质数

这正是质数被称为算术“原子”的原因:每个数都只有唯一一种构造配方,因此只要知道质数及其指数,就能知道这个数所有因数的信息。

存在性（最小反例法）： 假设存在不能写成质数乘积的整数 $n > 1$，并设 $m > 1$ 是其中最小的一个。由于每个质数本身就是一个质数的乘积，故 $m$ 必为合数，可写为满足 $1 < a, b < m$ 的整数之积 $m = a b$。由 $m$ 的最小性知 $a$ 与 $b$ 都是质数的乘积，从而它们的乘积 $m = a b$ 也是质数的乘积，矛盾。

欧几里得引理： 设质数 $p$ 满足 $p \mid a b$ 且 $p \nmid a$。因 $p$ 为质数且 $p \nmid a$，故 $\gcd(p, a) = 1$。由裴蜀定理，存在整数 $x, y$ 使得 $p x + a y = 1$。两边同乘 $b$ 得 $p(b x) + (a b)y = b$；由于 $p$ 同时整除 $p(b x)$ 与 $a b$，故 $p$ 必整除右边，即 $p \mid b$。

唯一性： 反证假设存在具有两种不同质因数分解的整数，取其中最小者 $n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$（按 $p_1 \le \cdots \le p_r$ 与 $q_1 \le \cdots \le q_s$ 排列）。由 $p_1 \mid q_1 q_2 \cdots q_s$ 并反复应用欧几里得引理可知，$p_1$ 必整除某个质数 $q_j$，从而 $p_1 = q_j \ge q_1$。由对称性又有 $q_1 \ge p_1$，故 $p_1 = q_1$。两边约去 $p_1$ 后得到更小的整数 $n / p_1 < n$ 仍具有两种不同分解，这与 $n$ 的最小性矛盾。

欧几里得的论证(约公元前300年):假设质数只有有限个 $p_1, p_2, \ldots, p_k$。把它们全部相乘再加 1:$N = p_1 p_2 \cdots p_k + 1$。$N$ 除以任意 $p_i$ 都余 1,所以没有一个 $p_i$ 能整除 $N$。但根据算术基本定理,$N$ 必定有某个质因数——而这个质因数不在原来的清单上。因此这份清单从来就不完整。

第一步（构造欧几里得数）： 设 $\{p_1, p_2, \dots, p_k\}$ 是任意给定的有限个质数集合。将列表中所有质数相乘再加 $1$，构造整数 $N = p_1 p_2 \cdots p_k + 1$。由 $p_1 \ge 2$ 可知 $N \ge 2 + 1 = 3 > 1$。

第二步（质因数的存在性）： 根据算术基本定理，每个整数 $N > 1$ 至少有一个质因数 $q$，即 $q \mid N$（若 $N$ 本身为质数则 $q = N$，若 $N$ 为合数则 $q < N$）。

**第三步（证明 $q$ 是新质数）：** 反证假设对某个下标 $i$ 有 $q = p_i$。于是 $q \mid p_1 p_2 \cdots p_k$，又因 $q \mid N$，故质数 $q$ 必整除两者的差 $q \mid (N - p_1 p_2 \cdots p_k) = 1$。但任何质数都满足 $q \ge 2$，这不可能成立。因此 $q \notin \{p_1, p_2, \dots, p_k\}$，证明了任何有限列表都无法囊括全部质数。