Dirichlet Convolution
Definition
$$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{xy=n}f(x)g(y)$$
Example
- $\sigma_0=1*1$
- $\sigma_1=I*1$
- $I=\varphi*1$
- $\epsilon(n)=\mu*1$
Property
- 交换律:$f*g=g*f$
- 结合律:$(f*g)h=f(g*h)$
- 分配律:$f*(g+h)=f*g+f*h$
- 单位元:$f*\epsilon=\epsilon * f=1$
Dirichlet Inversion
Proposition
对于任意数论函数,若 $f(1)\neq0$,则一定存在一个数论函数 $f^{-1}$,使得 $f*f^{-1}=\epsilon$,称 $f^{-1}$ 为 $f$ 的狄利克雷卷积的逆。
Proof.
$$f(n)=\begin{cases} \dfrac{1}{g(n)} & n=1\ -\dfrac{\sum_{k|n,k\neq n}f(k)g(\frac{n}{k})}{g(1)} & n\geq 2\end{cases}$$
Dirichlet Generating Function
Definition
定义数论函数 $f$ 的狄利克雷生成函数为
$$F(s)=\sum_{n=1}^{\infty}\dfrac{f(n)}{n^s}$$
Proposition
狄利克雷生成函数的卷积即为狄利克雷卷积。