狄利克雷卷积

Dirichlet 卷积

数论函数 \(f(n)\) 和 \(g(n)\) 的 Dirichlet 卷积（Dirichlet convolution），记作 \(f * g\)，定义为数论函数

\[(f * g)(n) = \sum_{k\mid n} f(k)g\left(\dfrac{n}{k}\right) = \sum_{k\ell=n} f(k)g(\ell). \]

Dirichlet 卷积是数论函数的重要运算．数论函数的许多性质都是通过这个运算挖掘出来的．

常见数论函数的 Dirichlet 卷积表示

单位函数 \(\varepsilon\) 是莫比乌斯函数 \(\mu\) 和常数函数 \(1\) 的 Dirichlet 卷积：

\[\varepsilon=\mu * 1 \iff\varepsilon(n)=\sum_{d\mid n}\mu(d). \]

除数个数函数 \(\tau\) 是常数函数 \(1\) 和它自身的 Dirichlet 卷积：

\[\tau=1 * 1 \iff \tau(n)=\sum_{d\mid n}1. \]

除数和函数 \(\sigma\) 是恒等函数 \(\mathrm{id}\) 和常数函数 \(1\) 的 Dirichlet 卷积：

\[\sigma=\mathrm{id} * 1 \iff\sigma(n)=\sum_{d\mid n}d. \]

欧拉函数 \(\varphi\) 是恒等函数 \(\mathrm{id}\) 和莫比乌斯函数 \(\mu\) 的 Dirichlet 卷积：

\[\varphi=\mathrm{id} * \mu \iff\varphi(n)=\sum_{d\mid n}d\cdot\mu\left(\frac{n}{d}\right). \]

性质

Dirichlet 卷积具有一系列代数性质．