次: 円順列への反転公式の応用 上: オイラーの関数 前: オイラーの関数

メビウスの反転公式

一般に自然数で定義されたふたつの関数 $F(n),\ G(n)$ に対して， 関数等式

$$\sum_{d\vert n}F(d)=G(n)$$ (2.23)

が成り立つとき，これを逆に解いて $F(n)$ を $G(n)$を用いて表すことができる．

そのためにメビウス(Möbius)の関数$\mu (n)$を次のように定義する．

$$\mu (n)= \left\{ \begin{array}{ll} 1&(n=1\ のとき)\... ...数の平方で割り切れるとき) \end{array} \right.$$

例 2.2.4  

$$\mu (1)=1,\ \mu (2)=-1,\ \mu (3)=-1,\ \mu (4)=0,\ \mu (5)=-1,\ \mu (6)=1,\ \cdots$$

補題 2
     $n>1$ なら

$$\sum_{d\vert n}\mu (d)=0$$

である．■

証明     $n>1$ であるから $n$ を素数のべきに因数分解して

$$n={p_1}^{e_1}{p_2}^{e_2}\cdots {p_k}^{e_k}$$

とする．よって

$$\sum_{d\vert n}\mu (d)=\sum^x\mu ({p_1}^{x_1}{p_2}^{x_2}\cdots {p_k}^{x_k})$$

ここで和は $0\le x_1 \le e_1,\ 0\le x_2 \le e_2,\ \cdots,\ 0\le x_k \le e_k$ の範囲内のすべての $x_1,\ x_2,\ \cdots,\ x_k$ を動く． この和の中で0になるもの，つまり各素数のべき指数が2以上のものを除くと，

$$\begin{eqnarray*} \sum_{d\vert n}\mu (d)&=&\mu(1)+\{\mu(p_1)+\mu(p_2)+\cdots+\... ...\mathrm{C}_2-{}_k \mathrm{C}_3+\cdots +(-1)^k\\ &=&(1-1)^k=0 \end{eqnarray*}$$

□

この $\mu (n)$ を用いると $F(n),\ G(n)$ に関する問題を解くことができる．

定理 20 (メビウスの反転公式)

整数で定義された二つの関数 $F(x),\ G(x)$ について二つの命題：

$$\begin{array}{l} \displaystyle \sum_{d\vert n}F(d)=G(n)\... ...um_{d\vert n}\mu \left(\dfrac{n}{d} \right)G(d) \end{array}$$

は同値である．■

証明     すべての $n$ に対して第一式が成り立てば，それを第二式の右辺に代入して

$$\sum_{d\vert n}\sum_{\delta\vert d} \mu \left(\dfrac{n}{d} \right)F(\delta)$$

$\delta$ を固定し，$\delta|d|n$ であるように $d$ が動くと， $\dfrac{n}{d}$ は $\dfrac{n}{\delta}$ の約数全体を動く． したがって和の順序を逆にして

$$=\sum_{\delta\vert n}\left[ F(\delta)\sum_{\delta'\vert \frac{n}{\delta}}\mu (\delta')\right]$$

補題2 によってかっこ内の和で $\dfrac{n}{\delta}>1$ のものは0になり， $F(n)\mu (1)$のみが残る．

$$∴\quad \sum_{d\vert n}\mu \left(\dfrac{n}{d} \right)G(d)=F(n)$$

つぎにすべての $n$ に対して第二式が成り立てば，同様に

$$\begin{eqnarray*} \sum_{d\vert n}F(d) &=&\sum_{d\vert n}\sum_{\delta\vert d}... ...lta'\vert \frac{n}{\delta}}\mu(\delta')\right] G(\delta)=G(n) \end{eqnarray*}$$

□

特に $F(n)=\varphi(n)$ のときは $G(n)=n$ である． この結果，整数で定義された関数で定理19の等式(2.22) がすべての $n$ について成り立つものは オイラーの関数 $\varphi (n)$ のみであることが示された． そして

$$\varphi(n)=\sum_{d\vert n}\mu \left( \dfrac{n}{d} \right)d$$

となる．こちらから$\varphi (n)$を計算する． $n=p^{\alpha}q^{\beta}r^{\gamma}\cdots$ とすると

$$\begin{eqnarray*} \varphi(n)&=&\sum_{d\vert n}\mu \left( \dfrac{n}{d} \right)d... ...\left(1-\dfrac{1}{q}\right) \left(1-\dfrac{1}{r}\right)\cdots \end{eqnarray*}$$

となり定理18と同じ結果が得られる．

次: 円順列への反転公式の応用 上: オイラーの関数 前: オイラーの関数