当前位置：首页 > news >正文

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

news 来源：原创 2025/8/3 9:03:41

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{equation*} \begin{cases} 1 \quad d=1\\ (-1)^k\quad d=p_1p_2\cdots p_k\\ 0\quad \exists p \mid d \land p^{2} \mid d \end{cases} \end{equation*}$

2. 证明

充分性证明

已知
$=\sum_{d|n}g(d)=\sum_{d|n}g(\frac{n}{d})$
代入到结果
$\begin{align*} \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{align*}$
由于 $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{equation*} \begin{cases} 1 \quad n=1\\ 0 \quad n \ne1 \end{cases} \end{equation*}$
只用 $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)$

即
$=\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{align*} \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_{dd_1|n}\mu(\frac{n}{dd_1})f(d_1)\\ &=\sum_{d_1|n}\sum_{d|\frac{n}{d_1}}\mu(\frac{n}{dd_1})f(d_1)\\ &=\sum_{d_1|n}f(d_1)\sum_{d|\frac{n}{d_1}} \mu(\frac{n}{dd_1}) \end{align*}$
跟充分性证明类似，只有当 $n=d_1$ 时，内层 $\sum_{d|\frac{n}{d_1}}\mu(\frac{n}{dd_1})$ 的值才为 $1$

因此
$\sum_{d_1|n}f(d_1)\sum_{d | \frac{n}{d_1}}\mu(\frac{n}{dd_1})=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)$ 的集合。

从左到右
$\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)$
从右往左
$\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)$

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

4. 参考

百度百科

1. 定义

2. 证明

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

4. 参考

相关文章：