Part1.定义：
狄利克雷(Dirichlet)卷积是定义在数论函数上的一种二维运算，常常记为：
\(h\left ( x \right )=\sum_{ab=x}^{}f\left ( a \right ) * g\left ( b \right ) =\sum_{d|x}^{}f\left ( x \right ) * d\left ( \frac{x}{d} \right )\)
可简单记为：
\(h = f \times g\)
Part2.前置：
我们有必要先了解一些常见的积性函数：(有一些\(Latex\)实在打不出来)
- 1.单位函数
\(\varepsilon(n):=1(while \text(n==1))\)
\(\varepsilon(n):=0(otherwise)\)
-
2.幂函数
$\mathrm{Id}_ k (n) := n ^ k $ . 当 \(k=1\) 时为恒等函数 \(\text{Id}(n)\) ，当 \(k=0\) 时为常数函数 \(\bold1(n)\) -
3.除数函数
\(\sigma_k(n):=\sum_{d|n}d^k\) ，当 k=1 时为因数和函数 \(\sigma(n)\) ，当 \(k=0\) 时为因数个数函数 \(\sigma_0(n)\) -
4.欧拉函数
$\varphi\left ( n \right ) = \prod_{pi|n}^{} \left ( 1- \frac{1}{pi} \right ) $
这四个函数都是积性函数
积性函数：若函数 \(f(n)\) 满足 \(f(1)=1\) 且 \(\forall x,y\in\mathbf{N}^ * , \gcd(x,y)=1\) 都有 \(f(xy)=f(x)f(y)\)，则 \(f(n)\) 为积性函数。
其中1,2是完全积性函数
完全积性函数：若函数 \(f(n)\) 满足 \(f(1)=1\) 且 $\forall x,y\in\mathbf{N}^ * $ 都有 \(f(xy)=f(x)f(y)\)，则 \(f(n)\) 为完全积性函数。
Part3.性质
众所周知若 \(f(x)\) 和 \(g(x)\) 均为积性函数，则：\(h(x)=\sum_{d\mid x}f(d)g\left(\dfrac{x}{d}\right)\)也为积性函数,现在来证明这个性质：
证明：
设\(a,b\in\mathbf{N}^ * , \gcd(a,b)=1\)
有\(h(a)=\sum_{d\mid a}f(d)g\left(\dfrac{a}{d}\right)\)，
\(h(b)=\sum_{d\mid b}f(d)g\left(\dfrac{b}{d}\right)\),
\(h(ab)=\sum_{d\mid ab}f(d)g\left(\dfrac{ab}{d}\right)\)
\(h(a) * h(b) = \sum_{d\mid a}f(d)g\left(\dfrac{a}{d}\right)* \sum_{d\mid b}f(d)g\left(\dfrac{b}{d}\right)\)
\(= \sum_{d1 \mid a,d2 \mid b}f(d1)g\left(\dfrac{a}{d1}\right)* f(d2)g\left(\dfrac{b}{d2}\right)\)
\(= \sum_{d1 \mid a,d2 \mid b}f(d1 \times d2)g\left(\dfrac{a\times b}{d1\times d2}\right)\)
由\(\gcd(a,b)=1\),得\(d1\ne d2\)
故\(d1* d2|a* b\)
原式\(= \sum_{d \mid ab}f(d)g\left(\dfrac{ab}{d}\right)\)
\(= h(ab)\)
故当\(a,b\in\mathbf{N}^ * , \gcd(a,b)=1\)时，\(h(a)\times h(b)=h(ab)\)
狄利克雷卷积还有一些性质：
- 1.交换律：\(f * g = g * f\)。
- 2.结合律：\(( f * g ) * h = f * ( g * h )\)。
- 3.分配律：\((f + g) * h = f * h + g * h\)。
证明
1.交换律
\(f * g = \sum_{ab=x}f(a)g(b)\)
\({a\leftrightarrow b}\)
\(\sum_{ab=x}f(a)g(b)=\sum_{ba=x}f(b)g(a)\)
\(=g * f\)
2.结合律
\((f * g) * h=\sum_{ab=x}f(a)g(b) * h\)
\(= \sum_{xy=n}(\sum_{ab=x}f(a)g(b)) * h(y)\)
\(= \sum_{aby=x}f(a)g(b)h(y)\)
\({a\leftrightarrow y},{b\leftrightarrow a},{y\leftrightarrow b}\)
原式\(= \sum_{aby=x}g(a)h(b)f(y)\)
\(= f * ( g * h )\)
3.分配律
\((f * ( g + h ) ) ( n ) = \sum_{xy = n } f ( x )( g + h )( y )\)
\(=\sum_{ xy = n } ( f( x ) g( y ) + f( x ) h ( y ))\)
\(=\sum_{ xy = n } f ( x ) g ( y ) + \sum_{ xy = n } f ( x ) h ( y )\)
$=(f * g) ( n ) + ( f * h ) ( n ) $