莫比乌斯反演定理内容

定义相关函数与概念

设 (f(n)) 和 (g(n)) 是定义在正整数集合 (\mathbb{N}^+) 上的两个函数。 莫比乌斯函数 (\mu(n)) 定义如下：

• 当 (n = 1) 时，(\mu(1)=1)；
• 当 (n) 有平方因子（即 (n=m^{2}k)，其中 (m > 1)）时，(\mu(n)=0)；
• 当 (n = p_{1}p_{2}\cdots p_{s}) 为 (s) 个不同素数的乘积时，(\mu(n)=(- 1)^{s})。

莫比乌斯反演定理陈述

若函数满足： (g(n)=\sum_{d\mid n}f(d))，其中求和是对 (n) 的所有正因数 (d) 进行的，也就是说 (d) 遍历满足 (d\mid n)（(d) 能整除 (n)）的所有正整数 (d)。

则有： (f(n)=\sum_{d\mid n}\mu(d)g(\frac{n}{d}))

定理证明思路（简要）

• 从 (g(n)=\sum_{d\mid n}f(d)) 出发，将 (g(\frac{n}{d})) 展开，(g(\frac{n}{d})=\sum_{k\mid\frac{n}{d}}f(k))。
• 那么 (\sum_{d\mid n}\mu(d)g(\frac{n}{d})=\sum_{d\mid n}\mu(d)\sum_{k\mid\frac{n}{d}}f(k))。
• 通过交换求和次序，并利用莫比乌斯函数的性质 (\sum_{d\mid n}\mu(d)=\begin{cases}1, & n = 1\0, & n>1\end{cases}) 可以得到最终结果 (f(n))。

另一种形式

若函数满足 (g(n)=\sum_{n\mid m}f(m))（这里求和是对所有满足 (n\mid m) 的正整数 (m) 进行），则有 (f(n)=\sum_{n\mid m}\mu(\frac{m}{n})g(m))。