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

1 素数・素数べきでの値

$p$が素数なら、$1$から$p$の中で$p$と互いに素でないのは$p$自身だけなので$\varphi(p) = p - 1$。素数べき$p^k$でも同じ発想が使えます。$1$から$p^k$のうち$p$の倍数（すなわち$p^k$と互いに素でないもの）は$p, 2p, \dots, p^{k-1}\cdot p$の$p^{k-1}$個だけなので、

$$\varphi(p^k) = p^k - p^{k-1}$$

です。「素因数を持つものだけ除けばよい」という、素数べきならではの単純さです。

2 乗法性：中国剰余定理の直接の帰結

$\gcd(m,n)=1$なら$\varphi(mn) = \varphi(m)\varphi(n)$ が成り立ちます。これは前項の中国剰余定理そのものの応用です。中国剰余定理は「$x \bmod mn$」と「$(x \bmod m,\ x \bmod n)$のペア」を1対1に対応させます。この対応のもとで、$x$が$mn$と互いに素であることと、$x$が$m$とも$n$とも互いに素であることは完全に一致します（$mn$の素因数は$m$の素因数と$n$の素因数を合わせたものだから。実はこの同値だけなら$m, n$が互いに素でなくても成り立ち、互いに素という仮定が本当に効いているのは中国剰余定理の1対1対応のほうです）。だから「$mn$と互いに素な$x \bmod mn$」の個数と「$m$と互いに素な$x\bmod m$」と「$n$と互いに素な$x \bmod n$」のペアの個数は等しく、$\varphi(mn) = \varphi(m)\varphi(n)$が出ます。

3 公式にまとめる

素数べきでの値と乗法性を組み合わせると、$n = p_1^{k_1}\cdots p_r^{k_r}$のとき

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

とまとめられます（各素数べきの因子$\varphi(p^k) = p^k(1-1/p)$を掛け合わせただけです）。たとえば$360 = 2^3 \times 3^2 \times 5$なら

$$\varphi(360) = 360 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 96$$

4 美しい恒等式：$\sum_{d \mid n} \varphi(d) = n$

$n$の約数$d$すべてにわたる$\varphi(d)$の総和は、ちょうど$n$になります。証明は、分数$\frac{1}{n}, \frac{2}{n}, \dots, \frac{n}{n}$を全部既約分数に約分してみるという観察だけでできます。約分すると分母は必ず$n$の約数$d$のどれかになり、分母がちょうど$d$になる既約分数は、分子が$1$から$d$までで$d$と互いに素なもの——つまり$\varphi(d)$個だけ現れます。もとの分数は全部で$n$個あり、どの分数もちょうど1つの$d$に対応するので、

$$\sum_{d \mid n} \varphi(d) = n$$

が成り立ちます。$n=6$で確かめると、約数は$1,2,3,6$で$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(6) = 1+1+2+2=6$——ぴったり一致します。「互いに素かどうか」という乗法的な量を全約数にわたって足すと、もとの数そのものが復元される、という不思議な恒等式です。