φ(n)=d|nμ(d)nd


代数系入門 (松坂和夫) 第1章 §8 問題4 の解答です。

( n in mathbb{Z}^+ ) について ( varphi(n) = sum_{d|n} mu(d) frac{n}{d} ) を示します。

問題3 (整数論的関数の反転公式 メビウスの反転公式) より、 ( varphi ) をオイラーの関数として

[ G(n) = sum_{d|n} varphi(d) ]

とすれば、

[ varphi(n) = sum_{d|n} mu(d) Gleft(frac{n}{d}right) ]

となります。

また、 問題2 (約数についてのオイラー関数の総和は元の数になる) より

[ G(n) = n ]

です。

以上より

[ varphi(n) = sum_{d|n} mu(d) frac{n}{d} ]

となります。