狄利克雷卷积

狄利克雷卷积为算术函数提供一种自然的乘法结构，莫比乌斯函数反演公式在其中只是一个恒等式。

定义

算术函数 $f, g$ 的狄利克雷卷积为

$$(f * g)(n) = \sum_{d \mid n} f(d)\, g\!\left(\frac{n}{d}\right)$$

性质

• 交换、结合、对加法分配；单位元为 $\varepsilon(n) = [n=1]$（即 $n=1$ 时取 $1$，否则取 $0$）
• $1 * \mu = \varepsilon$，由此得莫比乌斯反演：$g = f * 1 \iff f = g * \mu$
• 积性函数的卷积仍为积性函数
• 狄利克雷级数相乘：$\displaystyle\sum_{n} \frac{(f*g)(n)}{n^s} = \left(\sum_{n} \frac{f(n)}{n^s}\right)\left(\sum_{n} \frac{g(n)}{n^s}\right)$

示例

• 除数函数 $d = 1 * 1$，因数和函数 $\sigma = \mathrm{id} * 1$（$\mathrm{id}(n) = n$）
• 欧拉函数 $\varphi = \mu * \mathrm{id}$，即 $\varphi(n) = \displaystyle\sum_{d\mid n} \mu(d)\,\frac{n}{d}$
• $d(12) = \displaystyle\sum_{d\mid 12} 1 = 6$；$\sigma(12) = 12+6+4+3+2+1 = 28$
• $\varphi(6) = \mu(1)\cdot 6 + \mu(2)\cdot 3 + \mu(3)\cdot 2 + \mu(6)\cdot 1 = 6-3-2+1 = 2$