莫比乌斯函数的由来及推导

网上搜莫比乌斯函数大多都没有写莫比乌斯函数的由来，而是直接写的定义式，这里对莫比乌斯函数进行推导。
学习了狄利克雷卷积后，我们来看以下几个常见的积性函数：

常函数: $I\left(n\right)=1$I(n)=1

单位元: $\xi \left(n\right)=[n=1](\xi \ast f=f)$ξ(n)=[n=1](ξ∗f=f)

莫比乌斯函数

对于一个数我们可以对其求逆，那么函数是否也可以求逆呢？答案是肯定的。我们看下面式子:

$f^{-1}\ast f=\xi$f−1∗f=ξ

$f^{-1}$f−1即是我们要的 $f$f的逆。

$f^{-1}\ast f=xi$f−1∗f=xi

$\Downarrow$⇓

$\forall n:{\sum }_{d\mid n}f\left(d\right)\ast f^{-1}\left(\frac{n}{d}\right)=[n=1]$∀n:∑d∣n​f(d)∗f−1(dn​)=[n=1]

若n=1

$f^{-1}\left(1\right)=\frac{1}{f\left(1\right)}$f−1(1)=f(1)1​

若n $≠1$≠​1

$f^{-1}\left(n\right)\ast f\left(n\right)=xi\left(n\right)$f−1(n)∗f(n)=xi(n)

$f^{-1}\left(n\right)\ast f\left(n\right)=0$f−1(n)∗f(n)=0

$\sum _{d\mid n}f\left(d\right)\ast f^{-1}\left(\frac{n}{d}\right)=0$d∣n∑​f(d)∗f−1(dn​)=0

将d=1从公式中提出来:
$f\left(1\right)\ast f^{-1}\left(n\right)+\sum _{d\mid n}f\left(d\right)\ast f^{-1}\left(\frac{n}{d}\right)=0 (d̸=1)$f(1)∗f−1(n)+d∣n∑​f(d)∗f−1(dn​)=0　　(d̸​=1)

$f^{-1}\left(n\right)=\frac{-\sum _{d\mid n}f\left(d\right)\ast f^{-1}\left(\frac{n}{d}\right)}{f\left(1\right)} (d̸=1)$f−1(n)=f(1)−∑d∣n​f(d)∗f−1(dn​)​　　(d̸​=1)

$f$f的逆即为这个式子了

那么接下来我们试试把 $f=I$f=I,n为质数的逆求出来试试:

$f^{-1}\left(p\right)=\frac{-f\left(p\right)\ast f^{-1}\left(1\right)}{f\left(1\right)}=-1$f−1(p)=f(1)−f(p)∗f−1(1)​=−1

看看 $p^2$p2:

$f^{-1}\left(p^2\right)=-\left(f\right(p^2)\ast f^{-1}(1)+f(p)\ast f^{-1}(p\left)\right)=0$f−1(p2)=−(f(p2)∗f−1(1)+f(p)∗f−1(p))=0

推广到 $p^k$pk

$f^{-1}\left(p^k\right)=-{\sum }_{i=1}^{k}f\left(p^i\right)\ast f^{-1}\left(p^{k-i}\right)$f−1(pk)=−∑i=1k​f(pi)∗f−1(pk−i)

不难看出:当k>1时， $f\left(p^k\right)$f(pk)就等于0了

所以对于合数 $n=p_1^{a_1}{p}_2^{a_2}...p_k^{a^k}$n=p1a1​​p2a2​​...pkak​ 有

$f^{-1}\left(n\right)=f^{-1}\left(p_1^{a_1}\right)f^{-1}\left(p_2^{a_2}\right)...f^{-1}\left(p_k^{a_k}\right)$f−1(n)=f−1(p1a1​​)f−1(p2a2​​)...f−1(pkak​​)　( $I^{-1}$I−1 为积性函数)

(积性函数的逆也是积性函数)
证明:
设 $f$f为积性函数,有
$f(i\ast j)=f\left(i\right)\ast f\left(j\right)$f(i∗j)=f(i)∗f(j)
$f(i\ast j)\ast f^{-1}(i\ast j)=\xi$f(i∗j)∗f−1(i∗j)=ξ
$f\left(i\right)\ast f^{-1}\left(i\right)\ast f\left(j\right)\ast f^{-1}\left(j\right)=\xi$f(i)∗f−1(i)∗f(j)∗f−1(j)=ξ
联立得:
$f(i\ast j)\ast f^{-1}(i\ast j)=f\left(i\right)\ast f^{-1}\left(i\right)\ast f\left(j\right)\ast f^{-1}\left(j\right)$f(i∗j)∗f−1(i∗j)=f(i)∗f−1(i)∗f(j)∗f−1(j)
$f^{-1}(i\ast j)=f^{-1}\left(i\right)\ast f^{-1}\left(j\right)$f−1(i∗j)=f−1(i)∗f−1(j)
证毕

如果 $a_n\>1$an​>1那么 $f\left(n\right)=0$f(n)=0

设 $f^{-1}=\mu (I^{-1}=\mu )$f−1=μ(I−1=μ),则有:

$\mu =\{\begin{array}{c}1 n=1\\ (-1{)}^k a^1=a^2=...=a^k=1\\ 0 otherwise\end{array}$μ=⎩⎪⎨⎪⎧​1　　　n=1(−1)k　　　a1=a2=...=ak=10　　　otherwise​

这个便是我们所知的莫比乌斯函数了。

积性函数的逆也是积性函数。

由我们的推导可知：

$\mu \ast I=\xi \xi \ast f=f$μ∗I=ξ　ξ∗f=f

设 $f\ast I=g$f∗I=g

$f\ast I\ast \mu =g\ast \mu$f∗I∗μ=g∗μ
公式

• $g\left(n\right)={\sum }_{d\mid n}f\left(d\right) \Leftarrow \Rightarrow f\left(n\right)={\sum }_{d\mid n}\mu \left(d\right)g\left(\frac{n}{d}\right)$g(n)=∑d∣n​f(d)　⇐⇒　f(n)=∑d∣n​μ(d)g(dn​)
• $g\left(n\right)={\sum }_{n\mid d}f\left(d\right) \Leftarrow \Rightarrow f\left(n\right)={\sum }_{n\mid d}\mu \left(d\right)g\left(\frac{d}{n}\right)$g(n)=∑n∣d​f(d)　⇐⇒　f(n)=∑n∣d​μ(d)g(nd​)

证明
方法一：逆推

• $\sum _{d\mid n}\mu \left(d\right)g\left(\frac{n}{d}\right)=\sum _{d\mid n}\mu \left(d\right)\sum _{x\mid \frac{n}{d}}f\left(x\right)=\sum _{x\mid n}f\left(x\right)\sum _{d\mid \frac{n}{x}}\mu \left(d\right)=\sum _{x\mid n}f\left(x\right)[\frac{n}{x}=1]=f\left(n\right)$d∣n∑​μ(d)g(dn​)=d∣n∑​μ(d)x∣dn​∑​f(x)=x∣n∑​f(x)d∣xn​∑​μ(d)=x∣n∑​f(x)[xn​=1]=f(n)

• 第二个式子同理

方法二：卷积法(因为好多人不知道 $\mu$μ的性质所以不知道这点)
$g=f\ast I$g=f∗I
$g\ast \mu =f\ast I\ast \mu$g∗μ=f∗I∗μ
$g\ast \mu =f\ast \xi$g∗μ=f∗ξ
$g\ast \mu =f$g∗μ=f
得证