$积性函数的定义$
若函数 $f(n)$ 满足 $f(1) = 1$ 且 $\forall x, y \in N^{*}, gcd(x, y) = 1$ 都有 $f(xy) = f(x)f(y)$ ,那么称 $f$ 为积性函数。
若函数 $f(n)$ 满足 $f(1) = 1$ 且 $\forall x, y \in N^{*}$ 都有 $f(xy) = f(x)f(y)$ ,那么称 $f$ 为完全积性函数。
$常用数论函数$
-
单位函数:$\varepsilon(n) = [n = 1]$
-
恒等函数:$\textrm{id}_k(n) = n^k$ ,$\textrm{id}_1(n)$ 通常记作 $\textrm{id}(n)$
-
常数函数:$1(n) = 1$
-
欧拉函数:$\varphi(n) = \sum_{d|n} [gcd(d, n) = 1]$
-
除数函数:$\sigma _k(n) = \sum_{d|n} d^k $ ,$\sigma_0(n)$ 通常记作 $d(n)$ ,$\sigma_1(n)$ 通常记作 $\sigma(n)$
-
莫比乌斯函数:$\mu (n) \left\\{ \begin{array}{a} 1 \ \ \ \ \ \ \ \ \ \ (n = 1) \\\ 0 \ \ \ \ \ \ \ \ \ \ (n含有平方因子)\\\ (-1)^k \ \ (n含有k个质因子) \\\ \end{array} \right. $
$狄利克雷卷积$
对于两个数论函数 $f(x)$ 和 $g(x)$ ,他们的卷积结果为:
$$h(n) = \sum_{d|n} f(d) g(\frac{n}{d})$$
狄利克雷卷积符号为 $*$ ,上式表示为:
$$h = f * g$$
$性质$
-
交换律:$f * g = g * f$
-
结合律:$(f * g) * h = f * (g * h)$
-
分配律:$f * (g + h) = f * g + f * h$
$数论函数的卷积公式$
-
$\mu * 1 = \varepsilon$
-
$\varphi * 1 = \textrm{id}$
-
$\mu * \textrm{id} = \varphi$
-
$1 * 1 = d$
-
$\textrm{id} * 1 = \sigma$