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

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

左辺の和について，$d$ が同じ素因数を $2$ つ以上含む項は消えるので，

素因数を含まないもの： $\mu(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$ ）

$\cdots$

よって，左辺は

$1-{}_k\mathrm{C}_1+{}_k\mathrm{C}_2-\cdots +(-1)^k{}_k\mathrm{C}_k\\ =(1-1)^k\\ =0$

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

$\displaystyle\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)g(d)\\ =\displaystyle\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)\sum_{d'\mid d}f(d')\\ =\displaystyle\sum_{d,d'}\mu\left(\dfrac{n}{d}\right)f(d')$

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

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

$f(d')\displaystyle\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)=\displaystyle\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)d=\displaystyle\sum_{d\mid n}\mu(d)\dfrac{n}{d}$

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