莫比乌斯反演

莫比乌斯函数

定义

莫比乌斯函数 \mu 的定义如下：

首先将 n 质因数分解，表示成

n = \prod_{i=1}^{k} {p_i}^{a_i}

则

\mu(n) = \{\begin{matrix} 1 & n=1\\ (-1)^k & a_i=1 \\ 0 & a_i>1\end{matrix}

（大括号崩了）

语言描述的话，就是当 n=1 时， \mu(n)=1 ；当 n 没有幂次大于平方的质因子（即 n 的所有质因子都不同）时，若 n 有奇数个质因子，则 mu(n)=-1 ，若 n 有偶数个质因子，则 mu(n)=1 ；否则 n 有幂次大于 2 的质因子，此时函数值 \mu(n)=0 。综上所述，莫比乌斯函数只有 1, -1, 0 这三种取值。

性质

• 性质一：对于任意一对互质的正整数 p,q ， \mu(p*q)=\mu(p)*\mu(q) 。所以 莫比乌斯函数是积性函数 。这一性质说明莫比乌斯函数可以被线性筛。

证明： 根据定义，可知若 p,q 中一个包含幂次大于平方的质因子，则它的莫比乌斯函数值为0 ，那么这两个函数值的乘积也为 0 。否则，因为 p,q 互质，所以它们没有相同的质因子。设 p,q 的质因子数分别为 f(p),f(q) ，则

f(p*q)=f(p)+f(q)

因为莫比乌斯函数的取值由质因子数的奇偶性决定，容易推出

\mu(p*q)=\mu(p)*\mu(q)

注意，对于不互质的正整数对，由于存在相同的质因子，此命题不成立。所以莫比乌斯函数是积性函数，但不是完全积性函数。

• 性质二：对于任意正整数 n ， \sum_{d|n}\mu(d)=[n=1] 。（这里的 [n=1] 表示当且仅当括号内条件成立时值为 1 ，否则为 0 。下文同。）

证明：

根据定义，当 n=1 时命题显然成立。

当 n>1 时， 将 n 按上文形式分解质因数。当 a_i>1 时函数值为 0 ，对整个式子的值没有贡献，可以不用考虑。我们只统计有多少个质因子的指数为 1 。那么上述式子可以化为：

\sum_{i=0}^k C_k^i*(-1)^i

由二项式定理得：

\sum_{i=0}^k\begin{pmatrix}k\\i\\\end{pmatrix}(-1)^i1^{k-i}=[(-1)+1]^k=0

• 性质三：对于任意正整数 n ， \sum_{d|n}\frac{\mu(d)}d=\frac{\varphi(n)}n

感觉这个结论并不怎么重要，证明暂时咕咕~~

待续。。