基本知识
狄利克雷卷积
定义在数论函数（在 \(\mathbb{Z_+}\) 上定义的函数）之间的一种二元运算。
定义：
\[(f * g)(n) = \sum_{xy=n}f(x)g(y) = \sum_{d \mid n}f(d)g\left(\frac{n}{d}\right) \]常见函数
单位函数
- \(\varepsilon(n) = [n = 1]\)
其中 \([P]\) 为艾弗森括号，当且仅当 \(P\) 为真时为 \(1\)，否则为 \(0\)。
常数函数
- \({\mathbf{1}}(n) = 1\)
幂函数
- \({\rm{Id}}_{k}(n) = n^k\)
特别的，当 \(k = 1\) 时为恒等函数 \({\rm{Id}}(n) = n\)，\(k = 0\) 时为常数函数 \(\mathbf{1}(n) = 1\)。
除数函数
- \(\sigma_{k}(n) = \sum\limits_{{d}\mid{n}} d^{k}\)
特别的，当 \(k = 1\) 时为因数和函数 \(\sigma(n) = n\)，\(k = 0\) 时为因数个数函数 \(\bm{1}(n) = 1\)。
欧拉函数
- \(\varphi(n) = \prod\limits_{p_{i} \in \mathbb{P}}(p_i - 1) = \sum\limits_{i = 1}^{n}[\gcd{(i, n)}=1]\)
欧拉函数代表不大于 \(n\) 的正整数与 \(n\) 互质的数的个数。
莫比乌斯函数
- \(\mu(n) = \begin{cases} 1 & n = 1 \\ (-1)^k & n \rm{不含平方数因子，且} n = p_{1}p_{2}\dots{p}_{k} \\ 0 & n \rm{含平方数因子}\end{cases}\)
积性函数与完全积性函数
积性函数
\(f(1) = 1\) 且当 \(\gcd{(a, b)} = 1\) 时满足 \(f(a)f(b) = f(ab)\) 的函数称积性函数。
完全积性函数
是积性函数的强形式，\(f(1) = 1\)，且 \(\forall a, ~ b \in D, ~ f(a)f(b) = f(ab)\) 的函数称完全积性函数。
狄利克雷运算的性质
封闭性
对于积性函数狄利克雷运算的结果一定是积性函数，假设下列讨论 \(\gcd{(a, b)} = 1\)。
\[\begin{aligned} (f * g)(a) \cdot (f * g)(b) &= \left( \sum_{d_1 \mid a} f(d_1)g\left(\frac{a}{d_1}\right) \right) \left(\sum_{d_2 \mid b} f(d_2) g\left(\frac{b}{d_2}\right)\right) \\ &= \sum_{d_1 \mid a}\sum_{d_2 \mid b} f(d_1)f(d_2) g\left(\frac{a}{d_1}\right) g\left(\frac{b}{d_2}\right) \\ &= \sum_{d_1d_2 \mid ab}f(d_1 d_2) g\left(\frac{ab}{d_1 d_2}\right) \\ &= \sum_{d \mid ab}f(d)g\left(\frac{ab}{d}\right) \\ &= (f * g)(ab) \end{aligned} \]