[math]Euler関数の和公式

【定理】正の整数$n$に対して、$n$と互いに素である$1$以上$n$以下の整数の個数を$\varphi (n)$とする。これはEulerのTotient関数と呼ばれ、以下が成り立つ。$$\sum _{d\mid n}\varphi (d)=n$$

【実験】$n=12$とすると、$n$の約数は$1,2,3,4,6,12$である。$$\varphi (1)=1$$ $$\varphi (2)=1$$ $$\varphi (3)=2$$ $$\varphi (4)=2$$ $$\varphi (6)=2$$ $$\varphi (12)=4$$であるから、確かに$$\sum _{d\mid n}\varphi (d)=n$$である。

【証明】$1\le a\le n$とする。$a$と$n$の最大公約数を$d$とすると、$\frac{a}{d}$と$\frac{n}{d}$は互いに素な整数である。また、$1\le \frac{a}{d}\le \frac{n}{d}$である。これを満たす$a$の個数は、定義から$$\varphi \left(\frac{a}{d}\right)$$となる。$n$のすべての最大公約数について同様に考えると、$$n=\sum _{d\mid n}\varphi \left(\frac{a}{d}\right)$$が分かる。$\frac{n}{d}$は$n$の約数であるから（最大公約数ではないが）、目標の式がわかる。