初等数论--莫比乌斯函数

1. 定义

一个比较重要的数论函数，定义如下

$$\mu (n)=\begin{array}{c}\{\begin{array}{ll}1& n=1\\ (-1{)}^k& n=p_1{p}_2\cdots p_k\\ 0& \exists p\mid n,p^2\mid n\end{array}\end{array}$$
举个例子
$$\mu (6)=1$$
$6=2\times 3$，因此6有两个不重复的质因数，$k=2$, $\mu (6)=(-1{)}^2=1$

另外一个例子
$$\mu (20)=0$$
$20=2^2\times 5$, 存在$p=2,2\mid 202^2=4\mid 20$，因此$\mu (20)=0$。

2. 性质

• 因数的函数和

$$\sum _{d|n}\mu (d)=\begin{array}{c}\{\begin{array}{l}1n=1\\ 0n\ne 1\end{array}\end{array}$$

$n=1$时，${\sum }_{d|n}\mu (d)=\mu (1)=1$。

当$n\ne 1$时，根据唯一分解定理$n=p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}$。

根据$\mu (n)$函数的性质，我们只需要考虑因数$d$，

满足$\forall p\mid d,p^2\nmid d$的情况。

也就是每个质因数选或者不选进行组合的情况，显然这是一个二项式系数的问题

$$\begin{array}{rl}\sum _{d|n}\mu (d)& =\left(\genfrac{}{}{0ex}{}{k}{0}\right)+\left(\genfrac{}{}{0ex}{}{k}{1}\right)(-1{)}^1+\cdots +(\genfrac{}{}{0ex}{}{k}{k})(-1{)}^k\\ & =(1+-1{)}^k\\ & =0\end{array}$$

• 积性函数

$$\gcd (a,b)=1,\mu (ab)=\mu (a)\mu (b)$$

当$a=1$或$b=1$时
$$\begin{gathered} \mu (ab)=\mu (a)\mu (1)=\mu (a) \\ \mu (ab)=\mu (b)\mu (1)=\mu (b) \end{gathered}$$
当$\exists p^2\mid a$或$p^2\mid b$时
$$\begin{gathered} \mu (a)=0or\mu (b)=0 \\ {p}^2\mid ab,\mu (ab)=\mu (a)\mu (b)=0 \end{gathered}$$
其他情况，假设
$$\begin{gathered} a=p_1{p}_2\cdots p_m \\ b=q_1{q}_2\cdots q_n \\ \mu (a)=(-1{)}^m,\mu (b)=(-1{)}^n \end{gathered}$$
由于$\gcd (a,b)=1$，因此
$$\begin{gathered} \forall 1\le i\le m,1\le j\le n;p_i\ne q_j \\ ab=p_1{p}_2\cdots p_m{q}_1{q}_2\cdots q_n \\ \mu (ab)=(-1{)}^{m+n} \end{gathered}$$
因此
$$\mu (a)\mu (b)=\mu (ab)=(-1{)}^{m+n}$$

莫比乌斯函数的积性得证。

3. 参考

百度百科