初等数论入门 Lesson 3 积性函数与狄利克雷卷积

积性函数

Multiplicative Function

积性函数定义：

$f(1)=1, \\ \forall a,b\;\gcd(a,b)=1 \Rightarrow f(ab)=f(a)f(b)$
完全积性函数（Completely Multiplicative Function）：

$f(1)=1\\ f(ab)=f(a)f(b)$

一些基础的函数（注意区分）：

常值函数： $1(n)=1$
恒等函数： $\text{id}(n)=n$
单位函数： $\varepsilon(n)=\left[n=1\right]$

约数个数 τ(n) 与约数和 σ(n)

记：

$n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r},\quad p_i \text{为互异素数},\ k_i \ge 1$

约数个数 $\tau(n)$

$\boxed{\tau(n)=\prod_{i=1}^r(k_i+1)}$

约数函数和 $\sigma(n)$

$\begin{align*} \sigma(n) &= \sum_{d\mid n} d \\ &= \prod_{i=1}^r \big(1 + p_i + p_i^2 + \dots + p_i^{k_i}\big) \\ &= \boxed{\prod_{i=1}^r \dfrac{p_i^{k_i+1} - 1}{p_i - 1}} \end{align*}$

二者均为积性函数，但并非完全积性函数。

欧拉函数 φ(n)

$\varphi(n)$ 表示 不超过 $n$ 且与 $n$ 互素的数的个数。

求解：

对于 $\varphi(p^k)$

$\boxed{\varphi(p^k)=p^k-p^{k-1}=p^k\left(1-\dfrac 1 p\right)}$

根据积性：

$\forall m,n\;\gcd(n,m)=1\\ \boxed{\varphi(mn)=\varphi(n)\varphi(n)}$

积性证明：

由中国剩余定理：

$\begin{cases} a \equiv x \pmod{m} \\ a \equiv y \pmod{n} \end{cases} \quad (\gcd(x, m) = 1, \gcd(y, n) = 1)$

在模 $mn$ 下有唯一解 $a$

因此 $\varphi(mn)$ 的解的几何就位 $\varphi(m)\times \varphi(n)$

通项公式

$\begin{align*} \varphi(n) &= \prod_{i=1}^{r} \varphi(p_i^{k_i}) \\ &= \prod_{i=1}^{r} p_i^{k_i} \left(1 - \frac{1}{p_i}\right) \\ &= \boxed{n \prod_{i=1}^{r} \left(1 - \frac{1}{p_i}\right)} \end{align*}$

$\varphi(n)$ 是积性函数，但不是完全积性函数

莫比乌斯函数 μ(n)

定义：

$\boxed{ \mu(n)= \begin{cases} 1, & n=1 \\ (-1)^r, & k_1=k_2=\cdots=k_r=1 \ (\text{即 }n\text{ 为 }r\text{ 个互异素数之积}) \\ 0, & \text{存在 }k_i\ge 2 \ (\text{即 }n\text{ 含平方因子}) \end{cases} }$