莫比乌斯反演

请先去初等数论学习一些常用记号。

莫比乌斯函数

\(\mu(n)\)

• \(\mu(1)=1\)
• 对 \(n\) 进行质因数分解：
  • 分解后有相同的质因数：\(\mu(n) = 0\)
  • 分解后无相同的质因数，有 \(k\) 个不同的质因数：\(\mu(n)=(-1)^k\)

性质

• \(n\in\mathbb{N^*},\sum_{d\mid n}\mu(d) = [n=1]\)

莫比乌斯反演

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

显然是狄利克雷卷积形式啊，所以可以简化一下。

\[ g(n) = \sum_{d\mid n} f(d) \to f = g * \mu \]

证明

我们知道，莫比乌斯函数有一个性质：\(n\in\mathbb{N^*},\sum_{d\mid n}\mu(d) = [n=1]\)，换成狄利克雷卷积的形式即是 \(\mu * I = \epsilon\)。

然后开始证明：

已知：

\[ g(n) = \sum _{d\mid n}f(d) \]

换成狄利克雷卷积形式，再在两边同时卷一个 \(\mu\)

\[ \begin{aligned} g &= f * I \newline g * \mu &= f * I * \mu \end{aligned} \]

利用结合律和上面的性质就可以证明完成了。

\[ \begin{aligned} g * \mu &= f * (I * \mu) \newline g * \mu &= f * \epsilon \newline g * \mu &= f \end{aligned} \]