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

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

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

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