莫比乌斯函数

莫比乌斯函数 $\mu(n)$ 是除数函数这类数论函数的"逆"，通过反演把关于因数的求和式倒过来。

定义

$$\mu(n) = \begin{cases}1, & n = 1\\ (-1)^r, & n = p_1p_2\cdots p_r \text{ 为 } r \text{ 个不同素数之积}\\ 0, & p^2 \mid n \text{（存在平方因子）}\end{cases}$$

性质

• 关键求和：$\displaystyle\sum_{d\mid n}\mu(d) = \begin{cases}1, & n=1\\ 0, & n>1\end{cases}$
• $\mu$ 是积性函数：$\gcd(m,n)=1 \Rightarrow \mu(mn)=\mu(m)\mu(n)$
• 莫比乌斯反演：若 $g(n) = \sum_{d\mid n} f(d)$，则 $f(n) = \sum_{d\mid n}\mu(d)\,g\!\left(\frac{n}{d}\right)$；反之亦然

示例

• $\mu(1)=1$，$\mu(2)=-1$，$\mu(3)=-1$，$\mu(4)=0$，$\mu(5)=-1$，$\mu(6)=1$
• 由欧拉函数的性质 $\sum_{d\mid n}\varphi(d) = n$，反演得 $\varphi(n) = \sum_{d\mid n}\mu(d)\frac{n}{d}$。取 $n=6$：$\mu(1)\cdot 6 + \mu(2)\cdot 3 + \mu(3)\cdot 2 + \mu(6)\cdot 1 = 6 - 3 - 2 + 1 = 2 = \varphi(6)$