Euler's totient functionとMobius functionの関係

最近見た式。

ぱっと見よく分からなかったので、ちょっと考えてみた。

例えばφ(10)について考えてみる。
これは、10と互いに素な10以下の正の整数の個数だ。

10以下の正の整数は10個ある。10 = 2 * 5なので、ここから2の倍数の個数10/2と、5の倍数の個数10/5を引く。

10 - 5 - 2 = 3となる。

ただし、10は2の倍数としても引かれているし、5の倍数としても引かれているので、1回余分に引かれていることになる。

よって
φ(10) = 10 - 5 - 2 + 1 = 4となる。

次に、n = 36を考えてみる。
φ(36)
= 36 - (36以下の2の倍数の個数) - (36以下の3の倍数の個数) + (36以下の6の倍数の個数)
= 36 - 36/2 - 36/3 + 36/6
= 12

となる。

36 = 2² * 3²と素因数分解できるので、4の倍数とか9の倍数とかについても考えたくなるが、これらは2の倍数、3の倍数ですでに数えられているので考えなくてよい。

つまり、平方数で割れる約数については考えなくてよい。
あとは、重複している部分を数えるために包除原理を使って、足したり引いたりすればよい。
この２つが感覚的に分かれば、最初に示した式はごく自然に見える。

一般に、
n = p1^k1 * p2^p2 * p3^k3 * ......
として

φ(n)
= n - n/p1  - n/p2 - n/p3 ..... + n / (p1 * p2) + n / (p1 * p3) + .... - n / (p1 * p2 * p3) .....
= ∑_{d | n} μ(d) n / d

となる。

(追記)
メビウスの反転公式を使うと、上式は


となる。同じく最近見かけて何故成り立つか分からなかった式だけど、ここでこう繋がったか。。