狄利克雷卷积及常见函数与莫比乌斯反演

QwQ 文章目前没有题目，只有理论知识

狄利克雷卷积

狄利克雷卷积（Dirichlet Convolution）在解析数论中是一个非常重要的工具.

使用狄利克雷卷积可以很方便地推出一些重要函数和公式，它在信息学竞赛和解析数论中至关重要.

狄利克雷卷积是定义在数论函数间的二元运算.

数论函数，是指定义域为 \(\mathbb{N}\)（自然数），值域为 \(\mathbb{C}\)（复数） 的一类函数，每个数论函数可以视为复数的序列.

它常见的定义式为：

狄利克雷卷积的一些定理

1. 若 \(f\)、\(g\) 都为积性函数，那么 \(f*g\) 也为积性函数

设 \(a\)、\(b\) 满足 \(gcd(a,b)=1\)，那么：

因为满足 \(a\)、\(b\) 互质，我们能将 \(\sum_{d_1|a}\sum_{d_2|b}\) 合并成 \(\sum_{d_1d_2|ab}\)，所以 \(f*g\) 也就是积性函数了.

2. 狄利克雷卷积具有交换律，即 \(f*g = g*f\)

显而易见

3. 狄利克雷卷积具有结合律，即 \((f*g)*h = f*(g*h)\)

如上，可知两式相等，结合律成立.

4. 狄利克雷卷积具有分配律，即 \((f+g)*h = (f*h)+(g*h)\)

总结一下：

1. 若 \(f\)、\(g\) 都为积性函数，那么 \(f*g\) 也为积性函数
2. 狄利克雷卷积具有交换律，即 \(f*g = g*f\)
3. 狄利克雷卷积具有结合律，即 \((f*g)*h = f*(g*h)\)
4. 狄利克雷卷积具有分配律，即 \((f+g)*h = (f*h)+(g*h)\)

关于“狄利克雷卷积”名称：

首先，狄利克雷（Gustav Lejeune Dirichlet）是 19 世纪德国的数学家，他是解析数论的创立者，是解析数论很多重要理论的提出者.

“狄利克雷卷积”亦可称为“狄利克雷乘积”，如果定义普通函数加法为数论函数间的“加”运算，那么这里的狄利克雷卷积就是数论函数的“乘”运算，并且，狄利克雷卷积满足交换律、结合律和分配律，其运算法则和普通算数乘法完全类似.

函数部分（均为积性函数

单位函数（单位元）\(\epsilon(n)\)

显然，有：

因此，单位函数 \(\epsilon(n)\) 称为狄利克雷卷积的单位元，它在狄利克雷卷积中的作用和 \(1\) 在普通乘法中的作用是类似的.

任何函数（包括 \(\epsilon\)）和 \(\epsilon\) 进行狄利克雷卷积，都得到该函数本身.

这里再引入一个东西：

狄利克雷逆

我们可以把这里的“逆”和“逆元”作类比.

例如，在普通运算中，一个数的“逆元”就是这个数的倒数；

在同余运算中，一个数的“逆元”在同个模的意义下，能使得它与这个数相乘的结果与 1 同余.

分别而言，如果我们规定 \(n\) 的逆元是 \(n^{-1}\)（这个符号是作为整体引入的，大多数情况下不能简单地理解为 \(\frac{1}{n}\)），那么就有这样两个式子：

\(n\times n^{-1} = 1\)

\(n\times n^{-1} \equiv 1 \quad \mod r\)

数字 \(1\) 代表两种运算中的单位元，所以说，逆元在类似乘法的运算中起着“倒数”的地位.

在狄利克雷卷积中，单位元为 \(\epsilon\)，我们定义狄利克雷逆如下：

函数 \(f^{-1}\) 就称为函数 \(f\) 的狄利克雷逆.

幂函数 \(Id_k(n)\)

特别的，有：

• \(k=1\) 时，为恒等函数 \(Id(n)\)，即 \(Id(n)=n\)；

• \(k=0\) 时，为常数函数 \(\pmb1(n)\)，即 \(\pmb1(n)=1\)；

  这里的常数函数 \(\pmb 1(n)\) 的函数名是加粗了的数字 \(1\)，不要和 \(1\) 弄混了.
  在某些场合，有人会用大写字母 \(I\) 来代替 \(\pmb 1\)，以防混淆，这里还是使用 \(\pmb 1\).

除数函数 \(\sigma_k(n)\)

直观上理解，\(\sigma_k(n)\) 表示 \(n\) 的所有因子的 \(k\) 次幂之和.

特别的，有：

• \(k=1\) 时，为因数函数 \(\sigma(n)\)，即 \(\sigma(n)=\sum_{d|n} d\)；
• \(k=0\) 时，为个数函数 \(d(n)\)，即 \(d(n)=\sum_{d|n} 1\)；

或者说，假设 \(n\) 分解为 \(\prod_{i=1}^m p_i^{c_i} \quad (c_i\in \mathbb{N}^*, p_i\in \mathbb{P})\)，那么：

• \(\sigma(n) = \prod_{i=1}^m(\sum_{j=0}^{c_i} p_i^j)\)
• \(d(n) = \prod_{i=1}^m (c_i+1)\)

欧拉函数 \(\varphi(n)\)

在数论中，对正整数 \(n\)，欧拉函数 \(\varphi(n)\) 是小于或等于 \(n\) 的正整数中与 \(n\) 互质的数的数目。此函数以其首名研究者欧拉命名，它又称为 \(\varphi\) 函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。

当 \(n\) 是质数的时候，显然有 \(\varphi(n) = n - 1\).

一些性质

1. 欧拉函数是积性函数

如果有 \(\gcd(a, b) = 1\)，那么 \(\varphi(a \times b) = \varphi(a) \times \varphi(b)\)；

特别地，当 \(n\) 是奇数时 \(\varphi(2n) = \varphi(n)\)；

2. \(n = \sum_{d \mid n}{\varphi(d)}\)

可以这样考虑：如果 \(\gcd(k, n) = d\)，那么 \(\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )\)。

如果我们设 \(f(x)\) 表示 \(\gcd(k, n) = x\) 的数的个数，那么 \(n = \sum_{i = 1}^n{f(i)}\)。

根据上面的证明，我们发现，\(f(x) = \varphi(\dfrac{n}{x})\)，从而 \(n = \sum_{d|n}\varphi(\dfrac{n}{d})\)，所以上式化为 \(n = \sum_{d|n}\varphi(d)\)。

3. 若 \(n = p^k\)，其中 \(p\) 是质数，那么 \(\varphi(n) = p^k - p^{k - 1}\)。

显然对于从 \(1\) 到 \(p^k\) 的所有数中，除了 \(p^{k-1}\) 个 \(p\) 的倍数以外其它数都与 \(p^k\) 互素，故 \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}\times(p-1)\)。

那么根据 1、3 性质可得：

4. 若 \(n\) 的分解为 \(\prod_{i=1}^m p_i^{c_i} \quad (c_i \in \mathbb{N}^*, p_i \in \mathbb{P})\)，则 \(\varphi(n) = n\times \prod_{i=1}^m \frac{p_i-1}{p_i}\)

证明略.

欧拉定理

若 \((a,m)=1\) ，则 \(a^{\varphi(m)}\equiv1\ (\text{mod}\ m)\)

扩展欧拉定理

莫比乌斯函数 \(\mu(n)\) 与 莫比乌斯反演（Möbius Inversion）

或者说，若 \(n\) 的分解为 \(\prod_{i=1}^m p_i^{c_i} \quad (c_i \in \mathbb{N}^*, p_i \in \mathbb{P})\)：

• 若 \(n=1\)，那么 \(\mu(n)=1\)；

• 若 \(\exists\ i\in[1,m]\)，使得 \(c_i \ge 2\)，那么 \(\mu(n)=0\)，否则 \(\mu(n)=(-1)^m\)；

一些性质

1. 莫比乌斯函数为积性函数；

2. \(\sum_{d\mid n}\mu(d)=\begin{cases}1&n=1\\0&n\neq 1\\\end{cases}\)

设 \(n=\prod_{i=1}^k{p_i}^{c_i},n'=\prod_{i=1}^k p_i\) 那么 \(\sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)=\sum_{i=0}^k \dbinom{k}{i}\cdot(-1)^i=(1+(-1))^k\)，根据二项式定理，易知该式子的值在 \(k=0\) 即 \(n=1\) 时值为 \(1\) 否则为 \(0\)，这也同时证明了 \(\sum_{d|n}\mu(d)=[n=1]=\varepsilon(n)\) 以及 \(\mu*1=\varepsilon\).

所以，莫比乌斯函数也可定义为函数 \(\pmb 1\) 的逆，即 \(\mu=\pmb 1^{-1}\)，那么就可以使用狄利克雷卷积来推导出莫比乌斯反演的结论了：

将其展开，即：

莫比乌斯反演扩展

对于数论函数 \(f,g\) 和完全积性函数 \(t\) 且 \(t(1)=1\):

常用狄利克雷卷积

\(\epsilon = \mu*1\)

上文：

设 \(n=\prod_{i=1}^k{p_i}^{c_i},n'=\prod_{i=1}^k p_i\) 那么 \(\sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)=\sum_{i=0}^k \dbinom{k}{i}\cdot(-1)^i=(1+(-1))^k\)，根据二项式定理，易知该式子的值在 \(k=0\) 即 \(n=1\) 时值为 \(1\) 否则为 \(0\)，这也同时证明了 \(\sum_{d|n}\mu(d)=[n=1]=\varepsilon(n)\) 以及 \(\mu*1=\varepsilon\).

\(d=\pmb1*\pmb1\)、\(\sigma = Id*\pmb1\)

均易证，略

\(Id=\varphi*\pmb1\)、\(\varphi =\mu*Id\)

上文：

\(Id(n) = n = \sum_{d \mid n}{\varphi(d)}\)

可以这样考虑：如果 \(\gcd(k, n) = d\)，那么 \(\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )\)。

如果我们设 \(f(x)\) 表示 \(\gcd(k, n) = x\) 的数的个数，那么 \(n = \sum_{i = 1}^n{f(i)}\)。

根据上面的证明，我们发现，\(f(x) = \varphi(\dfrac{n}{x})\)，从而 \(n = \sum_{d|n}\varphi(\dfrac{n}{d})\)。注意到约数 \(d\) 和 \(\dfrac{n}{d}\) 具有对称性，所以上式化为 \(n = \sum_{d|n}\varphi(d)\)。

而因为 \(\mu\) 是 \(\pmb 1\) 的逆，所以 \(\varphi*\pmb 1*\mu=Id*\mu=\varphi\)

热门相关：高人竟在我身边   顶楼的大象   学霸的黑科技系统   仙城之王   我在末世有套房