離散數學/算術函式

一個算術函式 是從正整數集合到複數集合的函式。重要算術函式的例子包括

尤拉 φ 函式

尤拉 φ 函式，$\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}})$.