メビウス関数(Mobius function)

メビウス関数の定義

任意の自然数 $n$ の約数すべてにわたって和をとったときに $0$ になるような関数 $f(n)$ があれば、数論にとって非常に有用な関数となります。1831 年、メビウスの輪で有名なドイツの数学者メビウス（August Ferdinand Möbius）がそのような条件を満たす関数 $\mu (n)$ を発表しました。

具体的に計算してみましょう。

 $n=1$ のときは定義によって $\mu (1)=1$
 $n=2$ は 1 個の素数の積なので $\mu (2)=(-1{)}^1=-1$
 $n=3$ のときも同様に $\mu (3)=-1$
 $n=4$ のときは平方因子 $2^2$ をもつので $\mu (4)=0$

以下同様に計算していくと、
$$\mu (5)=-1,\mu (6)=\mu (2\cdot 3)=(-1{)}^2=1,\mu (7)=-1,\cdots$$
のような値をとることがわかります。定義より明らかに素数 $p$ について
$$\mu (p)=-1,\mu (p^k)=0(k=2,3,\cdots )$$
が成り立ちます。

メビウス関数が乗法的であることを証明しておきます。

[証明] $a,b$ を素因数分解して
$$\begin{array}{rl}a=& p_1^{a_1}{p}_2^{a_2}\cdots p_i^{a_i}\\ b=& q_1^{b_1}{q}_2^{b_2}\cdots p_j^{b_j}\end{array}$$
のように表せたとします。$(a,b)=1$ なので、
$$p_1,p_2,\cdots ,p_i,q_1,q_2,\cdots ,q_j$$
の中に共通する素因数はないので、$a$ と $b$ の積をつくると
$$ab=p_1^{a_1}{p}_2^{a_2}\cdots p_i^{a_i}{q}_1^{b_1}{q}_2^{b_2}\cdots q_i^{b_i}$$
となります。$a_1,a_2,\cdots ,b_1,b_2$ のなかに 2 以上の値があるときは
$$\mu (a)\mu (b)=0=\mu (ab)$$
となります。$a_1=a_2=\cdots b_1=b_2=\cdots =1$ のときは
$$\mu (a)=(-1{)}^i,\mu (b)=(-1{)}^j,\mu (ab)=(-1{)}^{i+j}$$
となるので、
$$\mu (ab)=\mu (a)\mu (b)$$
が成り立ちます。（証明終）

たとえば $n=20$ のとき、
$$\mu (35)=\mu (5)\mu (7)=(-1)\cdot (-1)=1$$
のように計算できます。

メビウス関数の約数にわたる和

たとえば $n=12$ のとき、そのすべての約数について和をとると
$$\begin{array}{rl}\sum _{d|12}\mu (d)=& \mu (1)+\mu (2)+\mu (3)+\mu (4)+\mu (6)+\mu (12)\\ =& 1+(-1)+(-1)+0+(-1{)}^2+0=0\end{array}$$
となります。これは一般にも成り立つ定理です。

[証明] $n=1$ のときは定義より明らかです。$n\ne 1$ のとき
$$n=p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}$$
のように素因数分解されたとすると、その約数は
$$d=p_1^{x_1}{p}_2^{x_2}\cdots p_k^{a_k}(1\le x_i\le a_k)$$
で表されます。$x_i\ge 2$ であれば $\mu (d)=0$ なので、このようなケースを除いて、$x_i=0$ または $x_i=1$ についてのみ和をとると
$$\begin{array}{rl}\sum _{d|n}\mu (d)& =\mu (1)+\mu (p_1)+\mu (p_2)+\cdots +\mu (p_k)+\cdots \\ & +\mu (p_1{p}_2)+\mu (p_1{p}_3)+\cdots \\ & +\mu (p_1{p}_2{p}_3)+\mu (p_1{p}_3{p}_4)+\cdots \\ & +\cdots \cdots \cdots \\ & +\mu (p_1{p}_2\cdots p_k)\end{array}$$
ここでたとえば $\mu (p_1{p}_2)+\mu (p_1{p}_3)+\cdots$ は $k$ 個から異なる $2$ 個を取り出したときの組み合わせの和となっているので、
$$\begin{array}{rl}\sum _{d|n}\mu (d)=& 1+{}_k{\mathrm{C}}_1(-1)+{}_k{\mathrm{C}}_2(-1{)}^2+\cdots +{}_k{\mathrm{C}}_k\\ =& \{1+(-1){\}}^k=0\end{array}$$
となります。（証明終）

証明の最後のところでは 二項定理
$$(a+b{)}^n=\sum _{k=0}^n{}_n{\mathrm{C}}_k{a}^{n-k}{b}^k$$
を用いました。
　

$\mu (d)$と$\mu (n/d)$の約数にわたる和

たとえば $\mu (10/d)$ の約数にわたる和を計算してみると
$$\begin{array}{rl}\sum _{d|10}\mu \left(\frac{10}{d}\right)=& \mu \left(\frac{10}{1}\right)+\mu \left(\frac{10}{2}\right)+\mu \left(\frac{10}{5}\right)+\mu \left(\frac{10}{10}\right)\\ & =\mu (10)+\mu (5)+\mu (2)+\mu (1)=\sum _{d|10}\mu (d)\end{array}$$
のようになって $\mu (d)$ の和に等しくなります。一般的にも
$$\sum _{d|n}\mu \left(\frac{n}{d}\right)=\sum _{d|n}\mu (d)$$
という関係が成り立ちます。

メビウスの反転公式

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

[証明] $d|n\wedge e|d$ ならば
$$n=kd,d=le$$
とおけるので、
$$n=kle\therefore e|d$$
が成り立ちます。さらに
$$\frac{n}{d}=k,\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)$ によってどのように表されるかを述べているのが次の定理です。

[証明] (1) を (2) の右辺に代入すると
$$\sum _{d|n}\mu \left(\frac{n}{d}\right)[\sum _{e|d}f(e)]=\sum _{d|n}[\sum _{e|d}\mu \left(\frac{n}{d}\right)f(e)]$$
ここで先ほどの補題 D1
$$d|n\wedge e|d⟺e|n\wedge \frac{n}{d}\mid \frac{n}{e}$$
を用いて和の変数を置き換えると
$$\sum _{d|n}[\sum _{e|d}\mu \left(\frac{n}{d}\right)f(e)]=\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{array}{rl}g(n)=& \sum _{d|n}f(d)(1)\\ f(n)=& \sum _{d|n}\mu \left(\frac{n}{d}\right)g(d)(2)\end{array}$$
において $f(n)=\phi (n)$ とおくと、
$$g(n)=\sum _{d|n}\phi (d)=n$$
となるので、
$$\phi (n)=\sum _{d|n}\mu \left(\frac{n}{d}\right)d$$
$n=de$ とおくと

となって、メビウス関数と オイラー関数 を結びつけることができます。$n=12$ の場合で試してみます。
$$\begin{array}{rl}\phi (12)=& 12\sum _{d|12}\frac{\mu (d)}{d}\\ =& 12(\frac{\mu (1)}{1}+\frac{\mu (2)}{2}+\frac{\mu (3)}{3}+\frac{\mu (4)}{4}+\frac{\mu (6)}{6}+\frac{\mu (12)}{12})\\ =& 12(\frac{1}{1}+\frac{(-1)}{2}+\frac{(-1)}{3}+\frac{0}{4}+\frac{1}{6}+\frac{0}{12})=4\end{array}$$