除数函数

除数函数刻画一个整数的因数结构：$\tau(n)$ 统计正因数个数，$\sigma(n)$ 统计正因数之和。

定义

对正整数 $n$：

• 除数个数函数 $\tau(n) = \#\{d\in\mathbb{Z}^+ : d\mid n\}$
• 除数和函数 $\sigma(n) = \sum_{d\mid n} d$

性质

设 $n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ 为标准分解式（见算数基本定理），则

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

$$\sigma(n) = \prod_{i=1}^{r}\frac{p_i^{\alpha_i+1}-1}{p_i-1} = \prod_{i=1}^{r}\left(1+p_i+\cdots+p_i^{\alpha_i}\right)$$

• $\tau$ 与 $\sigma$ 都是积性函数：$\gcd(m,n)=1 \Rightarrow \tau(mn)=\tau(m)\tau(n)$，$\sigma(mn)=\sigma(m)\sigma(n)$
• $p$ 为素数时 $\tau(p)=2$，$\sigma(p)=p+1$；$\tau(p^k)=k+1$，$\sigma(p^k)=\dfrac{p^{k+1}-1}{p-1}$
• 若 $\sigma(n) = 2n$，则 $n$ 称为完全数，如 $6, 28$

示例

• $12 = 2^2\cdot 3$：$\tau(12)=(2+1)(1+1)=6$，$\sigma(12)=(1+2+4)(1+3)=7\cdot 4 = 28$
• $360 = 2^3\cdot 3^2\cdot 5$：$\tau(360)=(3+1)(2+1)(1+1)=24$，$\sigma(360)=15\cdot 13\cdot 6 = 1170$