一些数论函数及其运算¶

数论函数是一种以正整数为定义域的函数，是数论的重要工具。

数论函数¶

数论函数的定义域是 $\mathbb{N}^{+}$ ，不是连续函数。常见的数论函数有：

单位函数 $\epsilon(n)=[n=1]$
欧拉函数 $\varphi(n)=\sum\limits_{i=1}^n[(i,n)=1]$
恒等函数 $\operatorname{id}(n)=n$
常值函数 $1(n)=1$
莫比乌斯函数 $\mu(n)=\begin{cases}1&\text{if }n=1\\0&\text{if }p\text{ contains square prime divisor}\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}$ ，其中 $\omega(n)$ 代表 $n$ 的质因子个数。

这些函数都是积性函数。

除了我们之前介绍过的与欧拉定理有关的欧拉函数，其他的函数似乎都没有什么意义。事实上这些数论函数之间有着千丝万缕的联系。

定义两个数论函数 $f(n)$ 和 $g(n)$ 的狄利克雷卷积 $(f*g)(n)$ 为

$(f*g)(n)=\sum\limits_{d\mid n}f(d)g\left(\dfrac{n}{d}\right)$

事先了解生成函数（特别是狄利克雷型生成函数）有助于理解狄利克雷卷积。

狄利克雷卷积有非常优异的性质。它是离散卷积的一种，满足三种主要运算律：

正如 $1$ 是乘法的单位元（ $x\times 1=x$ ），单位函数 $\epsilon$ 是狄利克雷卷积的单位元（ $f*\epsilon=f$ ），任何数论函数 $f$ 与 $\epsilon$ 的狄利克雷卷积都是其本身。

莫比乌斯反演有两个形式，在此先介绍其第一个形式，即

$f(n)=\sum\limits_{d\mid n}g(n)\iff g(n)=\sum\limits_{d\mid n}\mu\left(\dfrac{n}{d}\right)f(d)$

用狄利克雷卷积的形式表达就是

$f=1*g\iff g=\mu * f$

我们当即发现，莫比乌斯函数 $\mu$ 与单位函数 $1$ 之间似乎有非常紧密的关系， $\mu$ 似乎可以被视作是 $1$ 的逆元。换句话讲

$1*\mu=\epsilon$

$\sum\limits_{d\mid n}\mu(d)=[n=1]$

由于含有平方质因子的数的莫比乌斯函数值为 $0$ ，设 $n=\prod {p_i}^{k_i},n^\prime=\prod p_i$ ，满足 $(1*\varphi)(n)=(1*\varphi)(n^\prime)$ 。

于是

$(1*\varphi)(n)=(1*\varphi)(n^\prime)=\sum\binom{\omega(n^\prime)}{i}\cdot (-1)^i=0^{\omega(n^\prime)}$

只有当 $n^\prime$ 的质因子数为 $0$ ，即 $n=n^\prime=1$ 时，才有 $(1*\varphi)(n)=1$ 。

当然，由于 $1*\varphi=\epsilon$ 和莫比乌斯反演的第一种形式是等价的，我们同时也证明了莫比乌斯反演的第一种形式。

$n=\sum\limits_{d\mid n}\varphi(d)$

用狄利克雷卷积的形式表达就是

$\operatorname{id}=\varphi*1$