莫比乌斯函数及莫比乌斯反演
莫比乌斯函数
定义
根据唯一分解定理,\(n=\prod_{i=1}^{k} p_i^{a_i}\)。 \(\mu\)定义为 \[\mu(n)=\begin{cases}\mu(1)=1\\ \mu(n)=(-1)^k,\quad \forall a_i=1\\ \mu(n)=0,\quad \exists a_i>1\end{cases} \]
性质
\(1\ast \mu=\varepsilon\) 即\(\sum_{d|n}\mu(d)=\varepsilon(n)\);
证明:
当\(n=1\)时,显然成立。
当\(n\not=1\)时:
\[ \begin{aligned}\sum_{d|n}\mu(d) & =\mu(1)+\mu(p_1)+\mu(p_2)+\ldots+\mu(p_k)+\mu(p_1p_2)+\cdots+\mu(p_1p_2\cdots p_k)\\ & =C_{k}^{0}+C_{k}^{1}(-1)+C_{k}^{2}(-1)^2+\cdots+C_{k}^{k}(-1)^k\\ & =\sum_{i=0}^{k}C_{k}^{i}(-1)^i\\ & =(1-1)^k=0\end{aligned} \]
\[\sum_{d|n} \frac{\mu(d)}{d}=\frac{\varphi(n)}{n}\]
求解算法
莫比乌斯反演
定义
\[f(n)=\sum_{d|n}g(d)\Leftrightarrow g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})\] 即\(f=g\ast 1\Leftrightarrow g=f\ast\mu\)
证明
\[f=g\ast 1\Leftrightarrow f\ast\mu=(g\ast 1)\ast\mu\Leftrightarrow f\ast\mu=g\ast(1\ast\mu)\Leftrightarrow f\ast\mu=g\ast\varepsilon\Leftrightarrow f\ast\mu=g\]
应用
证明\(n=\sum_{d|n}\varphi (d)\):
由莫比乌斯函数性质 2 移项,得:\(\varphi(n)=\sum_{d|n}(\mu(d)\frac{n}{d})\)
令\(f(n)=n,g(n)=\varphi(n)\),反演一下,\(n=\sum_{d|n}\varphi (d)\)。
莫比乌斯函数及莫比乌斯反演