\(\S 4\) 狄利克雷卷积
狄利克雷卷积
两个数论函数 \(f, g\) 的狄利克雷卷积定义为：
\[
(f * g)(n) = \sum_{d \mid n} f(d) \, g\!\left(\frac{n}{d}\right)
\]
基本性质： - 交换律：\(f * g = g * f\) - 结合律：\((f * g) * h = f * (g * h)\) - 单位元：\(\varepsilon\)（即 \(f * \varepsilon = f\)），其中 \(\varepsilon(n) = [n = 1]\) - 若 \(f(1) \neq 0\)，则 \(f\) 存在唯一的狄利克雷逆 \(f^{-1}\)，满足 \(f * f^{-1} = \varepsilon\)
证明
交换律
\[
\begin{aligned}
(f*g)(n)&=\sum_{d \mid n}f(d) \, g\!\left( \frac{n}{d} \right) \\
&= \sum_{\substack{d\mid n \\ dd'=n}} f\left(\frac{n }{d'}\right)\,g\!\left(d'\right) \\
&= \sum_{d'\mid n} g \left( d' \right)f \left( \frac{n }{d' } \right) \\
&= \left( g*f \right) (n)
\end{aligned}
\]
结合律
我们需要证明 \((f*g)*k=f*(g*k)\)
\(\text{设 } A(n)=(f*g)(n)\)
\[
\begin{aligned}
(A*k)(n)&=\sum_{a\mid n} A(a)k \left( \frac n a \right)\\
&= \sum_{a\mid n} \left[ (f*g)(a) \right] \cdot k \left( \frac n a \right) \\
&= \sum_{a\mid n} \sum_{b\mid a } f(b)\cdot g \left( \frac a b \right) \cdot k \left( \frac n a \right) \\
&= \sum_{abc=n} f(a)\,g(b)\,k(c)
\end{aligned}
\]
设 \(B(n)=(g*k)(n)\)
\[
\begin{aligned}
(f*B)(n) &= \sum_{a\mid n} f(a)\,B \left( \frac n a \right) \\
&= \sum_{a\mid n} f(a) \cdots
\end{aligned}
\]
\[
\text{笔者已经累了🥱🥱🥱, 这里剩余部分就交给读者自行证明了}
\]
~~这些话好像经常出现在某些教材，这里学习大师的语言艺术~~
定理 1
\[
\begin{equation*}
I(n)= \left[ \frac 1 n \right]
\end{equation*}
\]
对于所有的数论函数，均有 \((f*I)(n)=f(n)\)
证明：
\[
\begin{aligned}
(f*I)(n) &= \sum_{a\mid n}f(a)\cdot I \left( \frac n a \right) \\
&= \sum_{a\mid n} f(a)\cdot \left[ \frac a n \right]\\
&= \sum_{a\mid n}\left(f(a)\cdot \left[ \frac a n \right]=\begin{cases}
f(n)& a=n \\[4pt]
0& a<n
\end{cases}\right) \\
&= f(n) \quad \square
\end{aligned}
\]
定理 2
\[
\begin{gathered}
\text{设数论函数 } f(n) ,满足f(1)\neq 0 ,则存在唯一的数论函数 f^{-1}(n)称为f(n)的狄利克雷逆函数\\使得\ \displaystyle{(f*f^{-1})(n)=I(n)} \\
且 f^{-1}(n)=\begin{cases}
\cfrac 1 {f(1)} & n=1 \\[8pt]
\cfrac{-1}{f(1)}\sum\limits_{d\mid n,\, d\neq n} f \left( \frac n d \right)f^{-1}(d) & n>1
\end{cases}
\end{gathered}
\]
证明
\[
\begin{gathered}
当 n=1 时, \sum_{d\mid 1} f(d)\cdot f^{-1} \left( \frac 1 d \right) = I(1) =1 \\
\because\ f(1)\neq 0 \quad f^{-1}(1)= \cfrac{1}{f(1)} \quad f^{-1}(n)在n=1的值唯一 \\
假设结论对于所有小于n的正整数都成立,下证对n也成立 \\
\begin{aligned}
0 &= I(n)=(f*f^{-1})(n) =(f^{-1}*f)(n)\\
&= \sum_{d\mid n}f^{-1}(d)\cdot f \left( \frac n d \right)\\
&= \sum_{d\mid n,\, d\neq n} f^{-1}(d)\cdot f \left( \frac n d \right)+f^{-1}(n)f(1) \\
\end{aligned}
\end{gathered}
\]
\[
\because\ f(1)\neq 0 \quad \therefore\ f^{-1}(n)=\cfrac{-1}{f(1)} \sum_{d\mid n,\, d\neq n}f^{-1}(d)f \left( \frac n d \right) \quad \square
\]
欧拉—莫比乌斯关系的卷积表述
以下两条恒等式是整个初等数论最核心的结论，用卷积写出来既简洁又便于推导：
\[
\boxed{\varphi * \mathbf{1} = \mathrm{id}} \qquad \qquad \boxed{\mu * \mathbf{1} = \varepsilon}
\]
第一条的证明：\((\varphi * \mathbf{1})(n) = \sum_{d \mid n} \varphi(d) = n = \mathrm{id}(n)\)。
第二条的证明：\((\mu * \mathbf{1})(n) = \sum_{d \mid n} \mu(d) = [n = 1] = \varepsilon(n)\)。
从这两条出发，可以流水般推出其他关系：
| 关系 | 推导 |
|---|---|
| \(\varphi = \mu * \mathrm{id}\) | \(\varphi = \varphi * \varepsilon = \varphi * (\mathbf{1} * \mu) = (\varphi * \mathbf{1}) * \mu = \mathrm{id} * \mu\) |
| \(\mathrm{id} = \varphi * \mathbf{1}\) | 已证明 |
| \(\mathbf{1} * \mu = \varepsilon\) | 已证明 |
| \(\varphi(n) = n \sum_{d \mid n} \frac{\mu(d)}{d}\) | \(\varphi = \mu * \mathrm{id}\) 展开即得 |