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$