莫比乌斯函数

定义

莫比乌斯函数\(\mu(n)\)，当\(n=1\)时，\(\mu(n)=1\)；当\(n>1\)时，设\(n\)的唯一分解式为\(n=p_1^{c_1}\cdots p_k^{c_k}\)，则\(\mu(n)\)定义为
\(\mu(n)= \begin{cases} (-1)^k,c_1=c_2=\cdots=c_k=1 \\ 0, \exists\, c_i>1(1\leq i\leq k)\\ \end{cases}\)

性质

1. \(\sum\limits_{d|n}\mu(d)=\lfloor\dfrac{1}{n}\rfloor=[n=1]\)
   注：约定方括号[]中为一个命题，其结果为\(1\)（该命题为真），或为\(0\)（该命题为假）。例如\([p为质数]\)=\(\begin{cases} 1,p是质数 \\ 0,p不是质数 \\ \end{cases}\)
   证明：\(n=1\)时，显然成立；现设\(n>1\)，\(n\)的唯一分解式为\(n=p_1^{c_1}\cdots p_k^{c_k}\)，则
   \(\begin{aligned} \sum\limits_{d|n}\mu(d) =&\mu(1)+\mu(p_1)+\cdots+\mu(p_k)+\mu(p_1p_2)\\ &+\cdots +\mu(p_{k-1}p_k)+\cdots+\mu(p_1\cdots p_k)\\ =&1+\binom{k}{1}(-1)+\binom{k}{2}(-1)^2+\cdots+\binom{k}{k}(-1)^k\\ =&(1-1)^k=0 \end{aligned}\)
2. \(\varphi(n)=\sum\limits_{d|n}\mu(d)\dfrac{n}{d}\)
   证明：
   因为\(\varphi(n)=n\left(1-\dfrac{1}{p_1}\right)\cdots\left(1-\dfrac{1}{p_k}\right)\)，其中\(n=p_1^{c_1}\cdots p_k^{c_k}\)是\(n\)的标准分解式，利用\(\mu(n)\)，可得\(\varphi(n)=\sum\limits_{d|n}\mu(d)\dfrac{n}{d}\)。

莫比乌斯反演

观察这两个等式
\(\qquad\qquad\qquad\begin{aligned} n&=\sum\limits_{d|n}\varphi(d)=\sum\limits_{d|n}\varphi\left(\dfrac{n}{d}\right)\\ \varphi(n)&=\sum\limits_{d|n}\mu(d)\dfrac{n}{d}=\sum\limits_{d|n}\mu\left(\dfrac{n}{d}\right)d\\ \end{aligned}\)
考虑将其推广至一般情况

莫比乌斯变换

对于数论函数\(f(n),g(n)\)，若
\(\qquad\qquad \qquad\qquad f(n)=\sum\limits_{d|n}g(d)=\sum\limits_{d|n}g\left(\dfrac{n}{d}\right)\)
则称\(f(n)\)为\(g(n)\)的莫比乌斯变换，而\(g(n)\)为\(f(n)\)的莫比乌斯逆变换。

反演公式

若有两个数论函数\(f(n),g(n)\)满足
\(\qquad \qquad \qquad \qquad f(n)=\sum\limits_{d|n}g(d)\qquad \qquad (1)\)
则有
\(\qquad \qquad \qquad \qquad g(n)=\sum\limits_{d|n}\mu(d)f\left(\dfrac{n}{d}\right) \qquad \qquad (2)\)
反过来，若满足\((2)\)，则\((1)\)也成立。
证明： 若\(f(n),g(n)\)满足\((1)\)，则
\(\qquad \qquad \begin{aligned} \sum\limits_{d|n}\mu(d)f\left(\dfrac{n}{d}\right)&=\sum\limits_{d|n}\mu(d)\sum\limits_{d'|\frac{n}{d}}g(d')\\ &=\sum\limits_{dd'|n}\mu(d)g(d')\\ &=\sum\limits_{d'|n}\sum\limits_{d|\frac{n}{d'}}\mu(d)g(d')\\ &=\sum\limits_{d'|n}g(d')\sum\limits_{d|\frac{n}{d'}}\mu(d)\\ &=g(n)\\ \end{aligned}\)
\(\qquad\)反过来，设\(f(n),g(n)\)满足\((2)\)，同法可证
\(\qquad \qquad \begin{aligned} \sum\limits_{d|n}g(d)&=\sum\limits_{d|n}g\left(\dfrac{n}{d}\right)\\ &=\sum\limits_{d|n}\sum\limits_{d'|\frac{n}{d}}\mu\left(\dfrac{n}{dd'}\right)f(d')\\ &=\sum\limits_{dd'|n}\mu\left(\dfrac{n}{dd'}\right)f(d')\\ &=\sum\limits_{d'|n}f(d')\sum\limits_{d|\frac{n}{d'}}\mu\left(\dfrac{n}{dd'}\right)\\ &=f(n)\\ \end{aligned}\)

莫比乌斯函数与莫比乌斯反演

原文：https://www.cnblogs.com/yydyz/p/10447805.html