初等数论--莫比乌斯反演

1. 定义

假设$f(n)g(n)$是定义在正整数上的两个函数 ，且

$$f(n)=\sum _{d|n}g(d)=\sum _{d|n}g(\frac{n}{d})$$
那么
$$g(n)=\sum _{d|n}\mu (d)f(\frac{n}{d})=\sum _{d|n}\mu (\frac{n}{d})f(d)$$

其中$\mu (d)$是莫比乌斯函数
$$\mu (d)=\begin{array}{c}\{\begin{array}{l}1d=1\\ (-1{)}^{k}d=p_1{p}_2\cdots p_k\\ 0\exists p\mid d\wedge p^2\mid d\end{array}\end{array}$$

2. 证明

充分性证明

已知
$$f(n)=\sum _{d|n}g(d)=\sum _{d|n}g(\frac{n}{d})$$
代入到结果
$$\begin{array}{rl}\sum _{d|n}\mu (d)f(\frac{n}{d})& =\sum _{d|n}\mu (d)\sum _{d_1|\frac{n}{d}}g(d_1)\\ & =\sum _{d|n}\sum _{d_1|\frac{n}{d}}\mu (d)g(d_1)\end{array}$$
由于$d{d}_1$都是$n$的因子，因此根据对称性我们可以交换求和的顺序
$$\sum _{d|n}\sum _{d_1|\frac{n}{d}}\mu (d)g(d_1)=\sum _{d_1|n}\sum _{d|\frac{n}{d_1}}\mu (d)g(d_1)$$
将$g(d_1)$放到外层，内层变成莫比乌斯函数求和
$$\sum _{d_1|n}\sum _{d|\frac{n}{d_1}}\mu (d)g(d_1)=\sum _{d_1|n}g(d_1)\sum _{d|\frac{n}{d_1}}\mu (d)$$
根据莫比乌斯函数性质
$$\sum _{d|n}\mu (d)=\begin{array}{c}\{\begin{array}{l}1n=1\\ 0n\ne 1\end{array}\end{array}$$
只用$d_1=n$时内层${\sum }_{d|\frac{n}{d_1}}\mu (d)=1$, 因此

$$\sum _{d_1|n}g(d_1)\sum _{d|\frac{n}{d_1}}\mu (d)=g(n)$$

即
$$g(n)=\sum _{d|n}\mu (d)f(\frac{n}{d})$$
充分性证明完成。

必要性证明

已知
$$g(n)=\sum _{d|n}\mu (d)f(\frac{n}{d})=\sum _{d|n}\mu (\frac{n}{d})f(d)$$
代入到${\sum }_{d|n}g(d)$
$$\begin{array}{rl}\sum _{d|n}g(d)& =\sum _{d|n}g(\frac{n}{d})\\ & =\sum _{d|n}\sum _{d_1|\frac{n}{d}}\mu (\frac{\frac{n}{d}}{d_1})f(d_1)\\ & =\sum _{d{d}_1|n}\mu (\frac{n}{d{d}_1})f(d_1)\\ & =\sum _{d_1|n}\sum _{d|\frac{n}{d_1}}\mu (\frac{n}{d{d}_1})f(d_1)\\ & =\sum _{d_1|n}f(d_1)\sum _{d|\frac{n}{d_1}}\mu (\frac{n}{d{d}_1})\end{array}$$
跟充分性证明类似，只有当$n=d_1$时，内层${\sum }_{d|\frac{n}{d_1}}\mu (\frac{n}{d{d}_1})$的值才为$1$

因此
$$\sum _{d_1|n}f(d_1)\sum _{d|\frac{n}{d_1}}\mu (\frac{n}{d{d}_1})=f(n)$$

即
$$f(n)=\sum _{d|n}g(d)$$

必要性得证。

$Q.E.D$

3. 关于交换求和顺序的说明

在充分性证明中，我们交换了$d_{1}d$内外层的顺序，我们在此简单的证明下

$$\sum _{d|n}\sum _{d_1|\frac{n}{d}}\mu (d)g(d_1)=\sum _{d_1|n}\sum _{d|\frac{n}{d_1}}\mu (d)g(d_1)$$

$L(d,d_1)$表示左边求和的所有二元组$(d,d_1)$的集合。

$R(d,d_1)$表示右边求和的所有二元组$(d,d_1)$的集合。

从左到右
$$\begin{gathered} \forall (d,d_1)\in L(d,d_1):d\mid n,d_1\mid \frac{n}{d}\Rightarrow d\mid \frac{n}{d_1} \\ (d,d_1)\in R(d,d_1) \end{gathered}$$
从右往左
$$\begin{gathered} \forall (d,d_1)\in R(d,d_1):d_1\mid n,d\mid \frac{n}{d_1}\Rightarrow d_1\mid \frac{n}{d} \\ (d,d_1)\in R(d,d_1) \end{gathered}$$

因此$L(d,d_1)=R(d,d_1)$，所以可以进行求和顺序的交换。

4. 参考

百度百科