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

この記事ではメビウス関数について解説します。

前半はメビウス関数の定義と簡単な性質です。後半はメビウスの反転公式という美しい定理とその応用例を解説します。

メビウス関数

まずメビウス関数 μ(n)\mu(n) を定義します。正の整数を与えると1,0,1-1,0,1 のいずれかを返す以下の関数です:

  • μ(1)=1\mu(1)=1
  • nn がある素数 pp22 回割り切れるとき μ(n)=0\mu(n)=0
  • nn が相異なる kk 個の素数の積であるとき μ(n)=(1)k\mu(n)=(-1)^k

μ(9)=0\mu(9)=0μ(12)=0\mu(12)=0μ(6)=1\mu(6)=1μ(30)=1\mu(30)=-1

メビウス関数の性質

定理

22 以上の任意の整数 nn について,

dnμ(d)=0\displaystyle\sum_{d\mid n}\mu(d)=0

dn\displaystyle\sum_{d\mid n} とは,nn の全ての約数 dd について和をとるという意味です。証明は定義に従って計算するだけです。

証明

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

左辺の和について,

  • dd が同じ素因数を 22 つ以上含む項は消える。

  • 素因数を含まないもの: μ(1)\mu(1) の1個 (値は 11

  • 素因数をちょうど 11 つ含むもの: μ(p1),,μ(pk)\mu(p_1),\cdots,\mu(p_k)kk 個(値は全て 1-1

  • 素因数をちょうど 22 つ含むもの: μ(p1p2),,μ(pk1pk)\mu(p_1p_2),\cdots,\mu(p_{k-1}p_k)kC2{}_k\mathrm{C}_2 個(値は全て 11

  • \vdots

よって,左辺は

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

ちなみに n=1n=1 のとき,定理の式の左辺の値は 11 になります。

メビウスの反転公式

f(n),g(n)f(n),g(n) を正の整数から実数(複素数でもよい)への関数とします。

メビウスの反転公式

g(n)=dnf(d)g(n)=\displaystyle\sum_{d\mid n}f(d) ならば, f(n)=dnμ(nd)g(d) f(n)=\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)g(d) と表される。

g=fg=f の和」という形の式を「f=gf=g の和」という形の式に「反転」できるという公式です。

証明

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

dnμ(nd)g(d)=dnμ(nd)ddf(d)=d,dμ(nd)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}

ただし,最後の式の和は「dd'dd の約数かつ ddnn の約数,を満たす全ての dddd' のペア」について取る。

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

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

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

よって,d=nd'=n のときの項: f(n)f(n) が残る。

メビウスの反転公式の応用例

定理

11 から nn までの整数の中で nn と互いに素なものの数 ϕ(n)\phi(n) は,nn の素因数分解を p1e1pkekp_1^{e_1}\cdots p_k^{e_k} とすると,

n(11p1)(11pk) n\left(1-\dfrac{1}{p_1}\right)\cdots \left(1-\dfrac{1}{p_k}\right)

証明の概略

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

ϕ(n)=dnμ(nd)d=dnμ(d)nd \phi(n)=\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)d=\sum_{d\mid n}\mu(d)\dfrac{n}{d}

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

メビウスの反転公式は,より一般の半順序集合に拡張できます。そこから包除原理を導出したりできます。奥が深い。