算数基本定理

算数基本定理说明素数是构成整数的唯一"积木"。

定理

每个大于 $1$ 的整数 $n$ 都可以唯一地分解为有限个素数的乘积（不计顺序）：

$$n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$$

其中 $p_1 < p_2 < \cdots < p_r$ 为互不相同的素数，$\alpha_i$ 为正整数。该式称为 $n$ 的标准分解式。

推论

• $d\mid n$ $\iff$ $d$ 的标准分解式中每个素因子指数都不超过 $n$ 中对应的指数
• 正因数个数：$\tau(n) = \prod_{i=1}^{r}(\alpha_i + 1)$
• $\gcd(a,b)$ 与 $\operatorname{lcm}(a,b)$ 的素因子指数分别取对应指数的最小值与最大值（见最大公因数）
• 素数有无穷多个（见素数）

示例

• $360 = 2^3\cdot 3^2\cdot 5$，$\tau(360) = (3+1)(2+1)(1+1) = 24$
• 由 $360 = 2^3\cdot 3^2\cdot 5$，$84 = 2^2\cdot 3\cdot 7$，得 $\gcd(360,84) = 2^2\cdot 3 = 12$，$\operatorname{lcm}(360,84) = 2^3\cdot 3^2\cdot 5\cdot 7 = 2520$