离散数学/算术函数

一个算术函数 是从正整数集合到复数集合的函数。重要算术函数的例子包括

欧拉 φ 函数

欧拉 φ 函数，$\phi (n)$ 定义为小于 n 且与 n 互质的正整数的个数

$\varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),$

莫比乌斯函数

莫比乌斯函数，$\mu (n)={\begin{cases}1,&{\mbox{if }}n\;{\mbox{is square free with an even number of prime factors}}\\-1,&{\mbox{if }}n\;{\mbox{is square free with an odd number of prime factors}}\\0&{\mbox{otherwise}}\end{cases}}$

$e(n)={\begin{cases}1,&{\mbox{if }}n=1\\0,&{\mbox{otherwise}}\end{cases}}$

冯·曼戈尔特函数

冯·曼戈尔特函数，$\Lambda (n)={\begin{cases}\ln p,&{\mbox{if }}n=p^{k}{\mbox{ for some prime}}p{\mbox{and}}k\geq 1\\0,&{\mbox{otherwise}}\end{cases}}$

$\sigma _{k}(n)=\sum _{d|n}d^{k}$

和

$\theta _{k}(n)=n^{k}$

这些函数中的许多是乘性的，也就是说它们满足 a(m)a(n)=a(mn)，当 m 和 n 互质时。如果一个函数满足 a(m)a(n)=a(mn) 即使 m 和 n 不互质，则称之为完全乘性的。为了定义一个乘性函数 a(n)，只需给出当 n 是素数的幂时的值即可；对于一个完全乘性函数，给出当 n 是素数时的值唯一地定义了该函数。

给定两个算术函数，它们的狄利克雷卷积定义为

$(a*b)(n)=\sum _{d|n}a(d)b({\frac {n}{d}})$

其中，求和是对 n 的所有因数 d 进行的。很容易证明

$(a*e)(n)=a(n)$,

也就是说，函数 e(n) 是狄利克雷卷积中的单位元。另一个基本的事实是，狄利克雷卷积是可交换的和结合的。

同样很容易证明，在狄利克雷卷积下，乘法函数构成一个群，换句话说，除了 e(n) 是单位元和结合律外，还具有以下性质

• 对于任何乘法函数 a，都存在一个乘法函数 b，使得 (a * b) = e

和

• 两个乘法函数的狄利克雷卷积也是乘法函数。

关于冯·曼戈尔特函数最重要的一个事实是

$\sum _{d|n}\Lambda (n)=\ln n$.

莫比乌斯函数的重要性源于以下事实

$\sum _{d|n}\mu (n)=e(n)$,

因此，如果 $f(n)=\sum _{d|n}g(d)$，则 $g(n)=\sum _{d|n}f(d)\mu ({\frac {n}{d}})$.