数论函数基础

数论函数是定义在 上的函数。

对两个数论函数可以求和、积和 Dirichlet 卷积。卷积定义为：它满足交换律、结合律、对加法的分配律。它的单位元是 一个满足 的数论函数 存在卷积逆（容易递推地构造），因而所有这样的函数构成交换群。

称一个（满足 ）的数论函数 是

• 积性函数，如果 s.t. ，有 ；其由素数幂处的值确定。
• 完全积性函数，如果 ；其由素数处的值确定。 积性在加法、乘法、卷积、卷积逆下保持，完全积性在加法、乘法下保持。

常见的数论函数包括：

• 不同素因子个数 ，它是一个加性函数
• 完全积性函数
  • 单位函数
  • 幂函数
• 积性函数
  • （ 的卷积逆）Möbius 函数
  • 除数函数
    • 因数个数
    • 因数和
  • 欧拉函数
    • 它满足

称与 的卷积为 Möbius 变换。由于有恒等式 ，有如下命题：

Theorem (Möbius inversion). 若 ，则 ，即