§A4.8オイラー関数 φ とその乗法性

証明.§A4.2 定理 2.2により、$p^k$の素因数は$p$だけである。したがって、整数が$p^k$と互いに素でないことと、その整数が$p$の倍数であることは同値である。$1$以上$p^k$以下の$p$の倍数は$p,2p,\ldots,p^{k-1}p$の$p^{k-1}$個なので、

となる。$k=1$とすると、$\varphi(p)=p-1$を得る。▨

証明.$m=1$または$n=1$の場合は、$\varphi(1)=1$から等式が従う。以下では$m,n\ge2$とする。§A4.6 補題 2.1により、法$mn$の剰余類と、法$m$の剰余類と法$n$の剰余類の組は一対一に対応する。整数$x$が$mn$と互いに素であることは、$x$が$m,n$の両方と互いに素であることと同値である。実際、§A4.2 定理 2.2により、$mn$の素因数は$m$の素因数と$n$の素因数を合わせたものである。また、$x\equiv r\pmod m$ならば$x,r$と$m$の公約数は一致するので、$m$と互いに素かどうかは剰余類によって定まる。法$n$でも同じことが成り立つ。

したがって、$mn$と互いに素な剰余類は、$m$と互いに素な剰余類と$n$と互いに素な剰余類の組に一対一に対応する。それぞれの個数を数えると、$\varphi(mn)=\varphi(m)\varphi(n)$となる。▨

証明. 相異なる素数のべきは互いに素なので、命題 3.1を繰り返し用いると

を得る。命題 2.1によって各因子を$p_i^{k_i-1}(p_i-1)=p_i^{k_i}(1-1/p_i)$と書くと、二つの表示が従う。▨

証明.$1\le k\le n$を満たす整数$k$に対し、$g=\gcd(k,n)$とおく。$k/n$を約分した既約分数は$(k/g)/(n/g)$であり、その分母$d=n/g$は$n$の正の約数である。

逆に、$n$の正の約数$d$と、$1\le u\le d$かつ$\gcd(u,d)=1$を満たす整数$u$を取る。$k=(n/d)u$とおくと$1\le k\le n$であり、$\gcd(k,n)=n/d$なので、$k/n$を約分すると$u/d$を得る。したがって、約分後の分母が$d$である分数はちょうど$\varphi(d)$個である。もとの$n$個の分数を約分後の分母によって分けて数えると、$\sum_{d\mid n}\varphi(d)=n$となる。▨