莫比乌斯函数
定义
根据唯一分解定理,\(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)\)。
3 comments