数学-数论-莫比乌斯函数及莫比乌斯反演

莫比乌斯函数

定义

根据唯一分解定理，\(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. \(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}\)

2. \(\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\)

应用

1. 证明\(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)\)。