Z/mZたちからなる短完全列の個数

$m$と$n$の最大公約数を$g$とおく.$f:\mathbb{Z}/m\mathbb{Z}\to \mathbb{Z}/n\mathbb{Z}$を$\mathbb{Z}-$準同型とする.$f([1])=[k]$,$0\leq k\leq n-1$とおく.準同型だから$0=f([m])=m\cdot f([1])=m\cdot [k]$.よって$mk$は$n$の倍数である.$mk=ns$,$s\in\mathbb{Z}$とする.$m=m'g,n=n'g$,$m',n'(\in\mathbb{Z})$は互いに素とおける.すると$m'k=n's$となり$k$は$ n'$の倍数である.よって$k$は$0,n',\dots,(g-1)n'$の$g$通りである.
逆にこのとき,$f([1])=[k]$によって定まる$f$はwell-definedである.実際,$a-a'\equiv 0$($\text{mod}\ m$)のとき$f(a)-f(a')\equiv 0$($\text{mod}\ n$)であればよいが$a-a'=mx$, $x\in\mathbb{Z}$とおくと$f(a)-f(a')=[kmx]=[km'gx]$であり$k$は$n'$で割り切れるから,これは$n$の倍数である.$\Box$

準同型定理から$\left(\mathbb{Z}/b\mathbb{Z}\right)/\text{ker}\ \psi \cong \mathbb{Z}/c\mathbb{Z}$なので$\dfrac{b}{|\text{ker}\ \psi|}=c$.
$b=c|\text{ker}\ \psi|=c|\text{Im}\ \phi|=ca$.

$\psi$の取り方は$[1]\mapsto 0,[1]$の$2$通り.そのうち全射となるのは後者のみなので$1$通り.
次に単射である$\phi$を全て求める.$k,i\in\mathbb{Z}$,$0\leq k\leq a-1$,$0\leq i\leq a-1$として$[1]\mapsto k[b]$とすると$ [i]\mapsto ik[b]$だから$ik$が$a$の倍数になるとき単射でなくなる.$k$が$a$の$2$以上の約数を因子に持てば$ki$が$a$の倍数となる$i$が存在する.それ以外の時は存在しない.よって互いに素であるときのみ$\phi$の核は自明である.
$k$と$a$が互いに素である時$ik[b]$は$b$の倍数で単射だから像は$\mathbb{Z}/ab\mathbb{Z}$における$b$の倍数全体に等しい.よって完全である.
以上から$\Phi$をオイラーのトーシェント関数として$\Phi(a)$通りある.