Dirichlet卷积

定义

定义数论函数 $_math_inline$f$math_inline_$ 和 $_math_inline$g$math_inline_$ 的狄利克雷卷积为 $_math_inline$h$math_inline_$ ，则 $_math_inline$h(n)=\sum_{d|n}f(d) g(\frac{n}{d})$math_inline_$ 记做 $_math_inline$h=f * g$math_inline_$ （ * 代表卷积）

性质

狄利克雷卷积满足交换律，结合律，对加法满足分配律

交换律： $_math_inline$f * g = g * f$math_inline_$

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

分配律： $_math_inline$f * (g+h)=f * g + f * h$math_inline_$

单位元： $_math_inline$f * e = e * f$math_inline_$

逆元：对于每一个 $_math_inline$f(1)\neq 0$math_inline_$ 的函数 $_math_inline$f$math_inline_$ ，都有 $_math_inline$f * g=\epsilon$math_inline_$

两个积性函数的狄利克雷卷积依旧为积性函数。 $_math_inline$f,g$math_inline_$ 为积性函数，则 $_math_inline$f * g$math_inline_$ 也为积性函数

$_math_inline$e$math_inline_$ 为单位元，它卷上任意的数论函数仍为原数论函数，简单来说，就是 $_math_inline$e(n)=[n=1]$math_inline_$

求一个函数的逆

只需定义： $_math_inline$g(n)=\frac{1}{f(1)}\left([n==1]-\sum_{i|n,i\neq1}f(i)g(\frac{n}{i})\right)$math_inline_$

这样的话： $_math_inline$\sum_{i|n}f(i)g(\frac{n}{i})=f(1)g(n)+\sum_{i|n,i\neq1}f(i)g(\frac{n}{i})=[n==1]$math_inline_$

常用的狄利克雷卷积

$_math_inline$(1\cdot\mu)=e$math_inline_$ ，因为 $_math_inline$\sum_{d|n}\mu(d)=[n=1]$math_inline_$

$_math_inline$\mu\cdot id=\phi$math_inline_$ ，将欧拉函数的通式展开即可得到次式。

$_math_inline$1\cdot id = \sigma$math_inline_$ $_math_inline$1\cdot 1 = \tau$math_inline_$

我们能够通过简单的狄利克雷卷积运算轻易的证出莫比乌斯反演

若有 $_math_inline$F(n)=\sum_{d|n}f(d)$math_inline_$

则有 $_math_inline$F=1\cdot f$math_inline_$ ，两边同时卷上 $_math_inline$\mu$math_inline_$ ，可得

$_math_inline$\mu \cdot F = \mu \cdot 1 \cdot f$math_inline_$

又因为 $_math_inline$1\cdot \mu =e$math_inline_$ ，所以 $_math_inline$f=\mu\cdot F$math_inline_$

即 $_math_inline$f(n)=\sum_{d|n}\mu(d)\cdot F(\frac{n}{d})$math_inline_$

我们甚至可以弄出一些很棒的东西，比如说

$_math_inline$id=id\cdot e=id\cdot\mu\cdot 1=\phi\cdot1$math_inline_$ $_math_inline$n=id(n)=\sum_{d|n}\phi(d)$math_inline_$ $_math_inline$\sigma=1\cdot id=1\cdot(1\cdot\phi)=(1\cdot 1)\cdot\phi=\tau\cdot\phi$math_inline_$ $_math_inline$\sigma(n)=\sum_{d|n}\tau(d)\cdot\phi(\frac{n}{d})$math_inline_$