【定理】正の整数\(n\)に対して、\(n\)と互いに素である\(1\)以上\(n\)以下の整数の個数を\(\phi(n)\)とする。これはEulerのTotient関数と呼ばれ、以下が成り立つ。$$\sum_{d\mid n}{\phi(d)} = n$$
【実験】\(n = 12\)とすると、\(n\)の約数は\(1, 2, 3, 4, 6, 12\)である。$$\phi(1) = 1$$ $$\phi(2) = 1$$ $$\phi(3) = 2$$ $$\phi(4) = 2$$ $$\phi(6) = 2$$ $$\phi(12) = 4$$であるから、確かに$$\sum_{d\mid n}{\phi(d)} = n$$である。
【証明】\(1\leq a\leq n\)とする。\(a\)と\(n\)の最大公約数を\(d\)とすると、\(\frac{a}{d}\)と\(\frac{n}{d}\)は互いに素な整数である。また、\(1\leq \frac{a}{d}\leq \frac{n}{d}\)である。これを満たす\(a\)の個数は、定義から$$\phi \left(\frac{a}{d}\right)$$となる。\(n\)のすべての最大公約数について同様に考えると、$$n = \sum_{d \mid n}{\phi \left(\frac{a}{d} \right)}$$が分かる。\(\frac{n}{d}\)は\(n\)の約数であるから（最大公約数ではないが）、目標の式がわかる。
コメント