Dirichlet 卷积

定义

对于两个数论函数 $f(x)$ 和 $g(x)$ ， 则它们的狄利克雷卷积得到的结果 $h(x)$ 定义为：

$h(x) = \sum_{d|x}f(d)g(\frac xd) = \sum_{ab = x} f(a)g(b)$

上式简记为

$h = f * g$

狄利克雷卷积是数论函数的重要运算，数论函数的许多性质都是通过这个运算挖掘出来的。

狄利克雷卷积与狄利克雷生成函数（DGF）密切相关。对于两个序列 $f, g$ ， 其狄利克雷生成函数之积，对应的是两者的狄利克雷卷积序列的狄利克雷生成函数：

$\tilde{F}(x)\tilde{G}(x) = \sum_{i} \sum_{j}\frac{f_i g_i}{(ij)^x} = \sum_{i} \frac{1}{i^x}\sum_{d|i}f_d g_\frac id$

性质

交换律： $f * g = g * f$ 。

结合律： $(f * g) * h = f * (g * h)$ 。

分配率： $(f + g) * h = f * h + g * h$。

等式的性质： $f = g$ 的充要条件是 $f * g = g * f$ ， 其中数论函数 $h(x)$ 要满足 $h(x) \ne 0$ 。

单位元： 单位函数 $\varepsilon$ 是 Dirichlet 卷积运算中的单位元，即对于任何数论函数 $f$ ， 都有 $f * \varepsilon = f$ 。

逆元： 对于任何一个满足 $f(x) \ne 0$ 的数论函数，如果有另一个数论函数 $g(x)$ 满足 $f * g = \varepsilon$ ， 则称 $g(x)$ 是 $f(x)$ 的逆元。由 等式的性质 可知，逆元是唯一的。（PS.狄利克雷卷积运算中的逆元，在狄利克雷生成函数中相当于倒数运算。）

容易构造出 $g(x)$ 的表达式为：

$g(x) = \dfrac{\varepsilon(x) - \sum_{d\mid x, d\ne 1}{f(d)g\left(\dfrac{x}{d}\right)}}{f(1)}$

重要结论

两个积性函数的 Dirichlet 卷积也是积性函数

证明：

设两个积性函数为 $f(x)$ 和 $g(x)$ ， 再记 $h = f * g$ 。

设 $\gcd(a, b) = 1$ ，则：

$h(a) = \sum_{d_1\mid a} f(d_1)g(\dfrac{a}{d_1}), h(b) = \sum_{d_2 \mid b}f(d_2)g(\frac{b}{d_2}),$

所以：

$\begin {aligned}h(a)h(b)&= \sum_{d_1\mid a}{f\left(d_1\right)g\left( \frac{a}{d_1}\right)}\sum_{d_2\mid b}{f(d_2)g\left(\dfrac b{d_2}\right)}\\ &= \sum_{d\mid ab}{f(d)g\left(\dfrac{ab}d \right)}\\&= h(ab) \end{aligned}$

综合以上两点，结论成立。

证毕

积性函数的逆元也是积性函数

证明略（滑稽）