积性函数与狄利克雷卷积
什么是卷积？
将两个函数复合后生成新函数的运算。
所谓复合，就是将两个函数对应位置的值进行一定的运算后得到新函数对应位置的值，具体见下文。
事实上，卷积是一种高等数学的代数语言。它不仅能够简化初等数学的代数推导，而且能解释 \(\mu(n),\varphi(n)\) 等数论函数的底层关系。
常见数论函数
定义域为正整数，值域为复数的函数被称为数论函数。
-
\(\varepsilon(n)\)：单位函数。\(\varepsilon(n) = [n = 1]\)。
-
\(\bold{1}(n)\)：常函数。\(\bold{1}(n) = 1\)。
-
\(\operatorname{id}(n)\)：恒等函数。\(\operatorname{id}(n) = n\)。
-
\(\operatorname{id_k}(n)\)：幂函数。\(\operatorname{id_k}(n) = n^k\)。
-
\(\sigma(n)\)：约数和函数。
-
\(\mu(n)\)、\(\varphi(n)\)、\(d(n)\)。
狄利克雷卷积
定义：
我们定义狄利克雷卷积的符号为 \(*\)，对于数论函数 \(f(n),g(n)\)，记其狄利克雷卷积为 \(h(n)=(f * g)(n)\)。则有：
\[h(n) = \sum_{d|n} f(d) \cdot g(\frac{n}{d})
\]
性质：
- 交换律
\[f * g = g * f
\]
证明：
\[f * g \\
= \sum_{d|n} f(d) \cdot g(\frac{n}{d}) \\
= \sum_{\frac{n}{d}|n} f(\frac{n}{d}) \cdot g(d) \\
= g * f
\]
这里运用到了 \(d\) 与 \(\frac{n}{d}\) 等价 的思想。