莫比乌斯函数
liduoduo2021
·
·
个人记录
莫比乌斯函数，也称为默比乌斯函数、缪比乌斯函数，用符号 \mu 表示，其定义如下：
\mu(x)=
\left\{\begin{matrix}
1,x=1 \\
0,p^i|x(i \ge 2) \\
(-1)^k,p^i|x(i \le 1)
\end{matrix}\right.
其中 k 为整除 x 的质数个数。
也就是当 x 为 1 时，该函数值为 1。
当 x 某个质因子的指数大于等于 2 该函数值为零，否则就为它质因数的个数。
性质：
\sum_{d|n}{\mu(d)}=(n==1)
即为当 n=1 时，上式的值为 1 ，否则为 0。
证明：
当 n=1 时，由定义可以推的：
\sum_{d|n}{\mu(d)}=\mu(1)=1
当 n\not=1 时，令 n=p_1^{c_1}\cdot p_2^{c_2}\cdot...\cdot p_k^{c_k},m=p_1 \cdot p_2\cdot...\cdot p_k，其中 p 为n 的质因数集，k 为质因数的个数。
由莫比乌斯定义若某个数质因数的质数大于 1 则它的函数值为 0 可知上式求和有很多部分的\mu为 0，具体的：
\sum_{d|n}{\mu(d)}=\sum_{d|m}{\mu(d)}=\sum_{i=0}^{k}{C^i_k \times (-1)^i}
由二项式定理得：
\sum_{i=0}^{k}{C^i_k \times (-1)^i}=\sum_{i=0}^{k}{C^i_k \times (-1)^i}\times1^{k-i}=[1+(-1)]^k=0
故 n\not=1 时 \sum_{d|n}{\mu(d)}=0。
证毕。