メビウスの反転公式の証明と応用

$n$ の素因数分解を $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ とする。

左辺の和について，

• $d$ が同じ素因数を $2$ つ以上含む項は消える。

• 素因数を含まないもの： $\mu(1)$ の1個 （値は $1$）

• 素因数をちょうど $1$ つ含むもの： $\mu(p_1),\cdots,\mu(p_k)$ の $k$ 個（値は全て $-1$）

• 素因数をちょうど $2$ つ含むもの： $\mu(p_1p_2),\cdots,\mu(p_{k-1}p_k)$ の ${}_k\mathrm{C}_2$ 個（値は全て $1$）

• $\vdots$

よって，左辺は

$$\begin{aligned} &1-{}_k\mathrm{C}_1+{}_k\mathrm{C}_2-\cdots +(-1)^k{}_k\mathrm{C}_k\\ &=(1-1)^k\\ &=0 \end{aligned}$$ となる。

$g(n)=\displaystyle\sum_{d\mid n}f(d)$ のとき，

$$\begin{aligned} &\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)g(d)\\ &=\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)\sum_{d'\mid d}f(d')\\ &=\sum_{d,d'}\mu\left(\dfrac{n}{d}\right)f(d') \end{aligned}$$

ただし，最後の式の和は「$d'$ が $d$ の約数かつ $d$ が $n$ の約数，を満たす全ての $d$ と $d'$ のペア」について取る。

$d'$ を固定して考えると，$d$ の動く範囲は $d'$ の倍数かつ $n$ の約数。つまり $\dfrac{n}{d}$ の動く範囲は $\dfrac{n}{d'}$ の約数。つまり $f(d')$ が登場する部分からは

$$f(d')\sum_{t}\mu(t)$$

という項が出てくる。ただし，$t$ は $\dfrac{n}{d'}$ の約数を動く。そして，$d'\neq n$ のとき，さきほど述べたメビウスの関数の性質によりこの和は $0$ である！

よって，$d'=n$ のときの項： $f(n)$ が残る。

$f(n)=\phi(n)$，$g(n)=n$ とおくと，オイラーのファイ関数のイメージと性質の「ファイ関数の和」で述べた性質により，$g(n)=\displaystyle\sum_{d\mid n}f(d)$ が成立する。よって，メビウスの反転公式より，

$$\phi(n)=\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)d=\sum_{d\mid n}\mu(d)\dfrac{n}{d}$$

メビウス関数の定義に従って最右辺を計算すると $$n\left(1-\dfrac{1}{p_1}\right)\cdots \left(1-\dfrac{1}{p_k}\right)$$ となる。