算术基本定理

算术基本定理说：每个大于 1 的正整数都能表示为素数乘积；若不计素数的排列次序，这种表示唯一。存在性与唯一性是两件事，不能因为分解算法每次似乎成功，就认为不同分解不可能发生。

存在性：分解合数

对整数 $n \geq 2$ 使用强数学归纳法。若 $n$ 为素数，它本身就是分解；若为合数，则 $n = a b$ ，其中 $2 \leq a, b < n$ 。按归纳假设， $a, b$ 各自有素数分解，合并后得到 $n$ 的分解。递归时因因子严格变小，不会停在没有分解的合数上。

唯一性：同一个素数不能消失

关键是欧几里得引理：若素数 $p ∣ a b$ ，则 $p ∣ a$ 或 $p ∣ b$ 。当 $p ∤ a$ 时， $gcd (p, a) = 1$ ；由贝祖等式可写 $p x + a y = 1$ ，乘 $b$ 后知 $p ∣ b$ 。

假设 $n = p_{1} \dots p_{r} = q_{1} \dots q_{s}$ 有两种素数分解。 $p_{1}$ 整除右边乘积，故必须整除某个 $q_{j}$ ；因 $q_{j}$ 也是素数，只能 $p_{1} = q_{j}$ 。两边约去这一个素数，再重复，最终两边剩余素数全部对应。 $360 = 2^{3} \cdot 3^{2} \cdot 5$ 展示把重复因子合并为指数的常见写法。1 不属于定理的分解对象，也不列为素数；否则随意插入若干个 1 会破坏唯一性的表述。

参考资料

MIT，Mathematics for Computer Science，Number Theory 章节。
MIT 18.781，初等数论讲义。
继续阅读：素数、贝祖等式、欧拉函数。