メビウスの反転公式

 今回は メビウスの反転公式 (Möbius inversion formula) を証明しますが、その前に準備として補題を1つ示しておきます。

[補題 D1] \[d\,|\,n\;\wedge\;e\,|\,d\quad\Longleftrightarrow\quad e\,|\,n\;\wedge\;\frac{n}{d}\mid\frac{n}{e}\]

[補題 D1 の証明] $d\,|\,n\;\wedge\; e\,|\,d$ ならば
 
\[n=kd,\quad d=le\]
とおけるので、
 
\[n=kle\quad\therefore e\,|\,d\]
が成り立ちます。さらに
 
\[\frac{n}{d}=k,\quad \frac{n}{d}=kl\]
なので、$\displaystyle\frac{n}{d}\mid\frac{n}{e}$ が成り立ちます。逆に $\displaystyle e\,|\,n\;\wedge\;\frac{n}{d}\mid\frac{n}{e}$ が成り立つとき、
 
\[\frac{n}{e}=m\frac{n}{d}\]
とおけるので、$d=me$ すなわち $e\,|\,d$ となります。(証明終)
 

メビウスの反転公式

 ある整数論的関数 $g(n)$ を別の関数 $f(n)$ の約数にわたる和によって
 
\[g(n)=\sum_{d|n}f(d)\]
のように定義されるとき、逆に $f(n)$ が $g(n)$ によってどのように表されるかを述べているのが次の定理です。

[定理 D11 メビウスの反転公式]
\[\begin{align*}g(n)=&\,\sum_{d|n}f(d)\qquad\qquad\quad (1)\\[6pt]
f(n)=&\,\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d)\qquad (2)\end{align*}\]

[定理 D11 の証明] (1) を (2) の右辺に代入すると
 
\[\sum_{d|n}\mu\left(\frac{n}{d}\right)\left[\sum_{e|d}f(e)\right]=\,\sum_{d|n}\left[\sum_{e|d}\mu\left(\frac{n}{d}\right)f(e)\right]\]
 ここで先ほどの補題 D1
 
\[d\,|\,n\;\wedge\;e\,|\,d\quad\Longleftrightarrow\quad e\,|\,n\;\wedge\;\frac{n}{d}\mid\frac{n}{e}\]
を用いて和の変数を置き換えると
 
\[\sum_{d|n}\left[\sum_{e|d}\mu\left(\frac{n}{d}\right)f(e)\right]=\sum_{e|n}\left[\sum_{(n/d)|(n/e)}\mu\left(\frac{n}{d}\right)\right]f(e)\]
 ここで [ ] の中は $n/e=1$ のときのみ $1$ となり、その他の場合は $0$ となります。よって $n=e$ より
 
\[\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d)=f(n)\]
となることが示されました。(証明終)
 

メビウス関数とオイラー関数

 メビウスの反転公式
 
\[\begin{align*}g(n)=&\,\sum_{d|n}f(d)\qquad\qquad\quad (1)\\[6pt]
f(n)=&\,\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d)\qquad (2)\end{align*}\]
において $f(n)=\varphi(n)$ とおくと、
 
\[g(n)=\sum_{d|n}\varphi(d)=n\]
となるので、
 
\[\varphi(n)=\sum_{d|n}\mu\left(\frac{n}{d}\right)d\]
 $n=de$ とおくと

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

となって、メビウス関数とオイラー関数を結びつけることができます。$n=12$ の場合で試してみます。
 
\[\begin{align*}\varphi(12)=&\,12\sum_{d|12}\frac{\mu(d)}{d}\\[6pt]
=&\,12\left(\frac{\mu(1)}{1}+\frac{\mu(2)}{2}+\frac{\mu(3)}{3}+\frac{\mu(4)}{4}+\frac{\mu(6)}{6}+\frac{\mu(12)}{12}\right)\\[6pt]
=&\,12\left(\frac{1}{1}+\frac{(-1)}{2}+\frac{(-1)}{3}+\frac{0}{4}+\frac{1}{6}+\frac{0}{12}\right)=4\end{align*}\]
 ≫ オイラーの定理 ≫ 初等整数論入門講座

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。