オイラー関数の和(約数で分類する)

方針

解答

⓪ 発想 — どう考え始めるか。 左辺は約数ごとの和、右辺は $n$ — 「$1$ から $n$ までの $n$ 個の整数を、過不足なく分類すると左辺になる」と読むのが筋だ。

分類の軸は $\gcd (k,n)$ の値。$\gcd (k,n)=d$ なら $k=dm$ で、$m$ は $\frac{n}{d}$ と互いに素。

つまり「$\gcd =d$ の組」の個数はちょうど $\phi \left(\frac{n}{d}\right)$。$d$ が約数を走れば $\frac{n}{d}$ も約数を走るから、和は $\sum \phi (d)$ に等しい。

① $\gcd$ で分類する。 $\{1,2,\dots ,n\}$ の各 $k$ を $\gcd (k,n)=d$ で分ける。$d$ は $n$ の約数を動く。$\gcd (k,n)=d$ なら $k=d\cdot m$ と書け、$\gcd (m,\frac{n}{d})=1$ かつ $1\le m\le \frac{n}{d}$。

② 各組の個数。 よって $\gcd (k,n)=d$ となる $k$ の個数は、$\frac{n}{d}$ 以下で $\frac{n}{d}$ と互いに素な $m$ の個数、すなわち $\phi \left(\frac{n}{d}\right)$。

③ 総和をとる。 すべての $k$ はちょうど1つの $d$ に属す(排反かつ全体)から $$n=\sum _{d\mid n}\phi \left(\frac{n}{d}\right)=\sum _{d\mid n}\phi (d)$$ (最後は $d$ と $\frac{n}{d}$ が約数全体を同じように動くため)。

まとめ $1$〜$n$ を $\gcd (k,n)$ で分類すると、$\gcd =d$ の組は $\phi (\frac{n}{d})$ 個。約数で足すと全体 $n$。約数を裏返せば ${\sum }_{d\mid n}\phi (d)=n$。数え上げの分類と整数(オイラー関数)の融合。$n=36$ なら約数の $\phi$ の和が $36$。

発展 — 一歩先へ。 この等式は「1の $n$ 乗根を位数で分類すると、位数 $d$ の根がちょうど $\phi (d)$ 個」という複素数平面の事実の言い換えでもある(既約分数 $\frac{k}{d}$ ⟺ 位数 $d$ の根 $e^{2\pi ik/d}$…を数IIIの言葉を借りずに言えば、円周の $n$ 等分点の「周期」による分類)。数論ではこの型の和の関係からメビウスの反転公式が生まれ、$\phi (n)$ の積公式へつながっていく。

別解

分数 $\frac{1}{n},\dots ,\frac{n}{n}$ を約分して仕分ける(1行の名証明)。 $n$ 個の分数

$$\frac{1}{n},\frac{2}{n},\frac{3}{n},\dots ,\frac{n}{n}$$

をすべて既約分数に約分する。約分後の分母は $n$ の約数 $d$ のどれかで、分母が $d$ になる分数は「分子が $d$ 以下で $d$ と互いに素」— ちょうど $\phi (d)$ 個ある(逆に、分母 $d$・既約の分数はすべてこのリストに現れる: $\frac{a}{d}=\frac{a(n/d)}{n}$)。

$n$ 個の分数が、約数ごとに $\phi (d)$ 個ずつに過不足なく仕分けられたのだから

$$\sum _{d\mid n}\phi (d)=n$$

$\gcd$ による分類(本解)と中身は同じだが、「約分」という誰もが知る操作に翻訳すると、証明が1枚の絵になる。$n=12$ で実際に12個の分数を約分してみると、分母 $1,2,3,4,6,12$ に $1,1,2,2,2,4$ 個 — 合計12個が確かめられる。