\(\S 5\) 莫比乌斯反演公式
定义
若数论函数 \(f(n)\) 和 \(g(n)\) 满足
\[
f(n) = \sum_{d\mid n} g(d)
\]
则称 \(f(n)\) 为 \(g(n)\) 的莫比乌斯变换，而 \(g(n)\) 为 \(f(n)\) 的莫比乌斯逆变换。
定理 1
设 \(f(n)\) 和 \(g(n)\) 为两个数论函数，则
\[
f(n) = \sum_{d\mid n} g(d) \quad \Longleftrightarrow \quad g(n) = \sum_{d\mid n} \mu(d) \, f\!\left(\frac{n}{d}\right)
\]
用卷积表述更为简洁：由 \(\mu * \mathbf{1} = \varepsilon\) 立得
\[
f = g * \mathbf{1} \quad \Longleftrightarrow \quad g = f * \mu
\]
证明
法一
首先证明 \(\mathbf{1} * \mu = \varepsilon\)：
\[
\begin{aligned}
(\mathbf{1} * \mu)(n) &= \sum_{d\mid n} \mu(d) \cdot \mathbf{1}\!\left( \frac n d \right) = \sum_{d\mid n} \mu(d) \\
&= \left[ \frac 1 n \right] \\
&= \varepsilon(n)
\end{aligned}
\]
若此处的证明看不太懂，请回看 莫比乌斯函数。
（\(\Rightarrow\)） 若 \(f = g * \mathbf{1}\)，则
\[
f * \mu = (g * \mathbf{1}) * \mu = g * (\mathbf{1} * \mu) = g * \varepsilon = g
\]
（\(\Leftarrow\)） 若 \(g = f * \mu\)，则
\[
g * \mathbf{1} = (f * \mu) * \mathbf{1} = f * (\mu * \mathbf{1}) = f * \varepsilon = f
\]
证毕。\(\square\)
里面 \(\mathbf{1}\)、\(\varepsilon\) 的含义参考 积性函数。
法二
充分性（\(\Rightarrow\)）：
设 \(f(n) = \sum_{d\mid n} g(d)\)，则
\[
\begin{aligned}
\sum_{d\mid n} \mu(d)\,f\!\left(\frac{n}{d}\right)
&= \sum_{d\mid n} \mu(d) \sum_{d'\mid \frac{n}{d}} g(d') \\
&= \sum_{dd'\mid n} \mu(d)\,g(d') \\
&= \sum_{d'\mid n} g(d') \sum_{d\mid \frac{n}{d'}} \mu(d) \\
&= \sum_{d'\mid n} g(d') \left[ \frac{d'}{n} \right] \\
&= g(n) \quad \square
\end{aligned}
\]
倒数第二步用到了莫比乌斯函数定理 1：\(\displaystyle\sum_{d\mid m} \mu(d) = \left[ \frac{1}{m} \right]\)，取 \(m = \dfrac{n}{d'}\) 即得 \(\displaystyle\sum_{d\mid n/d'} \mu(d) = \left[ \frac{d'}{n} \right]\)，仅当 \(d'=n\) 时为 \(1\)，其余为 \(0\)。
必要性（\(\Leftarrow\)）：
设 \(g(n) = \sum_{d\mid n} \mu(d)\,f\!\left(\frac{n}{d}\right)\)，则
\[
\begin{aligned}
\sum_{d\mid n} g(d)
&= \sum_{d\mid n} \sum_{d'\mid d} \mu(d')\,f\!\left(\frac{d}{d'}\right) \\
&= \sum_{ab\mid n} \mu(a)\,f(b) \qquad (\text{令 } a = d',\ b = d/d') \\
&= \sum_{b\mid n} f(b) \sum_{a\mid \frac{n}{b}} \mu(a) \\
&= \sum_{b\mid n} f(b) \left[ \frac{b}{n} \right] \\
&= f(n) \quad \square
\end{aligned}
\]