$\S 6$ 积性函数

定义

设 $f(n)$ 是定义在正整数上的函数，若对于任意互素的正整数 $m,n$（即 $\gcd(m,n)=1$），均有

\[ f(mn)=f(m)f(n) \]

则称 $f(n)$ 为积性函数。

若上式对任意正整数 $m,n$（不要求互素）都成立，则称 $f(n)$ 为完全积性函数。

常见积性函数速查

函数	记号	定义	积性类型
单位函数	$\varepsilon(n)$	$[n = 1]$	完全积性
常数函数	$\mathbf{1}(n)$	$1$	完全积性
恒等函数	$\mathrm{id}(n)$	$n$	完全积性
幂函数	$\mathrm{id}_k(n)$	$n^k$	完全积性
欧拉函数	$\varphi(n)$	$1 \sim n$ 中与 $n$ 互质的个数	积性
莫比乌斯函数	$\mu(n)$	见莫比乌斯函数章节	积性
除数函数	$\sigma_k(n)$	$\sum_{d \mid n} d^k$	积性
因子个数	$d(n)$	$\sigma_0(n)$	积性
因子和	$\sigma(n)$	$\sigma_1(n)$	积性

定理 1

\[ \begin{equation*} 若 f(n) 是积性函数（且不恒为零），则 f(1) = 1。 \end{equation*} \]

证明：取 $m = n = 1$，由 $\gcd(1, 1) = 1$ 及积性定义：

\[ f(1) = f(1 \cdot 1) = f(1) \cdot f(1) \]

若 $f(1) = 0$，则对任意 $n$ 有 $f(n) = f(n \cdot 1) = f(n) \cdot 0 = 0$（平凡零函数）。排除此退化情形，故 $f(1) = 1$。$\square$

定理 2：狄利克雷卷积保持积性

\[ \begin{equation*} 如果 f(n) 和 g(n) 是积性函数，那么 h(n) = (f * g)(n) = \sum_{d \mid n} f(d) g\!\left(\frac{n}{d}\right) 也是积性函数。 \end{equation*} \]

证明：设 $(m, n) = 1$，需要证明 $h(mn) = h(m) h(n)$。

\[ \begin{aligned} h(mn) &= (f * g)(mn) = \sum_{d \mid mn} f(d) g\!\left(\frac{mn}{d}\right) \\ &= \sum_{t_1 \mid m,\; t_2 \mid n} f(t_1 t_2) \, g\!\left(\frac{mn}{t_1 t_2}\right) \quad \text{(因为 } (m,n)=1 \text{，} mn \text{ 的每个因子唯一分解为 } t_1 t_2 \text{)} \end{aligned} \]

由于 $(t_1, t_2) = 1$ 且 $f, g$ 是积性函数，所以 $f(t_1 t_2) = f(t_1) f(t_2)$，同时：

\[ g\!\left(\frac{mn}{t_1 t_2}\right) = g\!\left(\frac{m}{t_1} \cdot \frac{n}{t_2}\right) = g\!\left(\frac{m}{t_1}\right) g\!\left(\frac{n}{t_2}\right) \quad \left(\text{注意 } \left(\frac{m}{t_1}, \frac{n}{t_2}\right) = 1\right) \]

代入得：

\[ \begin{aligned} h(mn) &= \sum_{t_1 \mid m,\; t_2 \mid n} f(t_1) f(t_2) \cdot g\!\left(\frac{m}{t_1}\right) g\!\left(\frac{n}{t_2}\right) \\ &= \left(\sum_{t_1 \mid m} f(t_1) g\!\left(\frac{m}{t_1}\right)\right) \cdot \left(\sum_{t_2 \mid n} f(t_2) g\!\left(\frac{n}{t_2}\right)\right) \\ &= h(m) \cdot h(n) \end{aligned} \]

故 $h(n)$ 是积性函数。$\square$

定理 3：狄利克雷卷积的逆元定理

如果 $g(n)$ 和 $h(n) = (f * g)(n)$ 都是积性函数，则 $f(n)$ 也是积性函数。

证明（反证法）：假设 $f(n)$ 不是积性函数，则一定存在一对互素的正整数 $(m, n) = 1$，使得 $f(mn) \neq f(m) f(n)$。

在所有这样的 $(m, n)$ 中，选取使得乘积 $mn$ 最小的一对。

由于 $h = f * g$ 是积性函数，且 $(m, n) = 1$：

\[ h(mn) = h(m) h(n) \tag{1} \]

另一方面，按狄利克雷卷积展开 $h(mn)$。因为 $(m, n) = 1$，$mn$ 的每个因子可唯一写成 $d_1 d_2$ 的形式（其中 $d_1 \mid m,\; d_2 \mid n$）：

\[ \begin{aligned} h(mn) &= \sum_{d \mid mn} f(d) g\!\left(\frac{mn}{d}\right) \\ &= \sum_{d_1 \mid m} \sum_{d_2 \mid n} f(d_1 d_2) \cdot g\!\left(\frac{m}{d_1}\right) g\!\left(\frac{n}{d_2}\right) \end{aligned} \]

从双重求和里把 $(d_1, d_2) = (m, n)$ 这一项单独提出来：

\[ h(mn) = f(mn) \cdot g(1) g(1) + \sum_{\substack{d_1 \mid m,\; d_2 \mid n \\ (d_1, d_2) \neq (m, n)}} f(d_1 d_2) \cdot g\!\left(\frac{m}{d_1}\right) g\!\left(\frac{n}{d_2}\right) \]

对于剩余项，因为 $d_1 d_2 < mn$，由"$mn$ 是最小反例"的选取可知 $f(d_1 d_2) = f(d_1) f(d_2)$。而 $g$ 是积性函数且 $g(1) = 1$，因此：

\[ \begin{aligned} h(mn) &= f(mn) + \sum_{d_1 \mid m} \sum_{d_2 \mid n} f(d_1) f(d_2) \cdot g\!\left(\frac{m}{d_1}\right) g\!\left(\frac{n}{d_2}\right) \;-\; f(m) f(n) \\ &= f(mn) + \left(\sum_{d_1 \mid m} f(d_1) g\!\left(\frac{m}{d_1}\right)\right)\! \left(\sum_{d_2 \mid n} f(d_2) g\!\left(\frac{n}{d_2}\right)\right) \;-\; f(m) f(n) \\ &= f(mn) + h(m) h(n) - f(m) f(n) \end{aligned} \]

结合 $(1)$ 式 $h(mn) = h(m) h(n)$，代入上式：

\[ h(m) h(n) = f(mn) + h(m) h(n) - f(m) f(n) \]

两边消去 $h(m) h(n)$，得：

\[ f(mn) = f(m) f(n) \]

这与一开始的假设 $f(mn) \neq f(m) f(n)$ 矛盾。因此不存在反例，$f(n)$ 必须是积性函数。$\square$

定理 4：积性函数的狄利克雷逆也是积性函数

若 $f(n)$ 是积性函数（且 $f(1) \neq 0$），则其狄利克雷逆 $f^{-1}(n)$ 也是积性函数。

证明：由狄利克雷逆的定义，

\[ (f * f^{-1})(n) = \varepsilon(n) = [n = 1] \]

$\varepsilon(n)$ 显然是积性函数（甚至完全积性）。已知 $f(n)$ 是积性函数，由定理 3（取 $g = f$、$h = \varepsilon$ 均为积性），即得 $f^{-1}(n)$ 是积性函数。$\square$

定理 5：完全积性的充要条件

设 $f(n)$ 是积性函数，则 $f(n)$ 是完全积性函数的充要条件是

\[ f^{-1}(n) = \mu(n) \cdot f(n) \]

其中 $f^{-1}$ 是 $f$ 的狄利克雷逆，$\mu$ 是莫比乌斯函数。

证明

（$\Rightarrow$）若 $f$ 完全积性，则 $f^{-1} = \mu \cdot f$

验证 $\mu \cdot f$ 恰为 $f$ 的狄利克雷逆：

\[ \begin{aligned} \bigl(f * (\mu \cdot f)\bigr)(n) &= \sum_{d \mid n} \mu(d) \cdot f(d) \cdot f\!\left(\frac{n}{d}\right) \\ &= \sum_{d \mid n} \mu(d) \cdot f\!\left(d \cdot \frac{n}{d}\right) \qquad \text{（$f$ 完全积性）}\\ &= f(n) \sum_{d \mid n} \mu(d) \\ &= f(n) \cdot [n = 1] \qquad \text{（$\mu * \mathbf{1} = \varepsilon$）}\\ &= \varepsilon(n) \end{aligned} \]

故 $f^{-1} = \mu \cdot f$。$\square$

反向

\[ \text{若 } f^{-1} = \mu \cdot f,\ \text{则 } f \text{ 完全积性} \]

先证一个引理。

引理：在 $f^{-1} = \mu \cdot f$ 且 $f$ 积性的条件下，对任意素数幂有 $f(p^\alpha) = f(p)^\alpha$。

引理证明：由卷积逆的定义 $f * f^{-1} = \varepsilon$，代入 $f^{-1} = \mu \cdot f$：

\[ \varepsilon(n) = \sum_{d \mid n} \mu(d) \cdot f(d) \cdot f\!\left(\frac{n}{d}\right) \]

取 $n = p^\alpha$（$\alpha \ge 1$）。$p^\alpha$ 的因子中 $\mu(d) \neq 0$ 的只有 $d = 1$ 和 $d = p$（含 $p^2$ 及以上有平方因子），故：

\[ \begin{aligned} 0 &= \mu(1) f(1) f(p^\alpha) + \mu(p) f(p) f(p^{\alpha-1}) \\ &= f(p^\alpha) - f(p) f(p^{\alpha-1}) \end{aligned} \]

因此 $f(p^\alpha) = f(p) f(p^{\alpha-1})$。递推：

\[ f(p^\alpha) = f(p)^{\alpha-1} \cdot f(p) = f(p)^\alpha \]

引理证毕。

回到必要性：任取 $m, n \in \mathbb{N}^+$，作标准分解（允许指数为零）：

\[ m = \prod_{i=1}^{s} p_i^{a_i}, \quad n = \prod_{i=1}^{s} p_i^{b_i}, \quad a_i, b_i \ge 0 \]

则 $mn = \prod_{i=1}^{s} p_i^{a_i + b_i}$。由 $f$ 的积性及引理：

\[ \begin{aligned} f(mn) &= f\!\left(\prod_{i=1}^{s} p_i^{a_i+b_i}\right) = \prod_{i=1}^{s} f(p_i^{a_i+b_i}) \\ &= \prod_{i=1}^{s} f(p_i)^{a_i+b_i} \qquad \text{（引理）}\\ &= \prod_{i=1}^{s} f(p_i)^{a_i} \cdot \prod_{i=1}^{s} f(p_i)^{b_i} \\ &= \prod_{i=1}^{s} f(p_i^{a_i}) \cdot \prod_{i=1}^{s} f(p_i^{b_i}) \\ &= f\!\left(\prod_{i=1}^{s} p_i^{a_i}\right) \cdot f\!\left(\prod_{i=1}^{s} p_i^{b_i}\right) \\ &= f(m) \cdot f(n) \end{aligned} \]

$m, n$ 任意，故 $f$ 是完全积性函数。$\square$

例题

问题：若 $f(n)$ 是积性函数，证明

\[ f(m) f(n) = f(\gcd(m, n)) \cdot f(\operatorname{lcm}(m, n)) \]

其中 $\gcd(m, n)$ 是最大公因数，$\operatorname{lcm}(m, n)$ 是最小公倍数。

证明：设 $m, n$ 的质因数分解为（允许指数为零）

\[ m = \prod_{i=1}^{s} p_i^{a_i}, \quad n = \prod_{i=1}^{s} p_i^{b_i}, \quad a_i, b_i \ge 0 \]

则

\[ \gcd(m, n) = \prod_{i=1}^{s} p_i^{\min(a_i, b_i)}, \qquad \operatorname{lcm}(m, n) = \prod_{i=1}^{s} p_i^{\max(a_i, b_i)} \]

由 $f$ 的积性：

\[ \begin{aligned} f(m) f(n) &= \left(\prod_{i=1}^{s} f(p_i^{a_i})\right) \left(\prod_{i=1}^{s} f(p_i^{b_i})\right) \\ &= \prod_{i=1}^{s} f(p_i^{a_i}) \, f(p_i^{b_i}) \end{aligned} \]

对每个 $i$，$\{a_i,\, b_i\}$ 与 $\{\min(a_i, b_i),\, \max(a_i, b_i)\}$ 是同一个多重集，因此

\[ f(p_i^{a_i}) f(p_i^{b_i}) = f(p_i^{\min(a_i, b_i)}) \, f(p_i^{\max(a_i, b_i)}) \]