01 / THE QUESTION
质数有可能全部数完吗?
质数是大于 1、只有 1 和自身两个正因数的正整数,例如 2、3、5、7、11、13。
2 是唯一的偶质数;1 不是质数。你可以继续找下去,发现质数之间的空隙有时很大。可是“空隙越来越大”,不等于“从某个地方开始再没有质数”。
我们要回答一个明确的问题:质数的总数是有限还是无限?如果能证明任何一张有限清单都必然遗漏质数,答案就是无限。
欧几里得《几何原本》第九卷命题 20 给出了质数不可能只有有限多个的论证。今天常见的“把所有质数相乘再加一”写法,是它的现代简洁表达。
THINK 01 / 概念关
先确认我们要证明的对象。
查看完整答案
选 C。质数大于 1 且只有两个正因数。2 满足定义;1 不满足,9 这种奇数也是合数。
02 / THE PLUS ONE
把名单上的质数全部相乘,然后加 1。
先假装质数只有 2、3、5 三个。虽然我们知道这份名单不全,但可以用它看清思路。
31 无法被 2、3、5 整除,而 31 本身又是质数。这份所谓“完整名单”被推翻了。
为什么偏偏加 1?因为乘积能被名单里的每一个质数整除,乘积加 1 再除以任何一个,都恰好余 1。这说明新数绝不可能含有名单上的质因数。
注意:“不能被名单里的质数整除”并不自动意味着 N 本身是质数。我们先别急着下结论。真正有威力的是“余 1”这个性质。
THINK 02 / 那个 1 有什么作用
想想除以 3 后的余数。
查看完整答案
选 B。P 含因数 3,能被 3 整除,所以 P+1 除以 3 余 1。
03 / THE PROOF
这次不假设名单缺了什么,而是假设它已经完整。
进入正式证明。我们不知道这张“完整名单”有多长,所以写成 p₁、p₂、…、pₖ,代表所有质数。假设它们只有有限多个。
- 假设质数只有有限多个。
把它们全部列为 p₁、p₂、…、pₖ。k 是某个正整数,名单中没有遗漏的质数。
- 造一个超过 1 的整数。
令 N=p₁p₂⋯pₖ+1。由于每个 pᵢ≥2,N>1。
- 证明名单中的任何质数都不整除 N。
对任意 pᵢ,乘积 p₁p₂⋯pₖ 都是 pᵢ 的倍数。因此 N 除以 pᵢ 余 1。
- 可是 N 必须有质因数。
每个大于 1 的整数都至少有一个质因数。如果 N 是质数,它自己就是;如果 N 是合数,继续分解,最终也会得到质数。因此 N 有某个质因数 q。
- 矛盾。
因为没有任何 pᵢ 整除 N,q 不可能等于名单里的任何 pᵢ;但名单被假设列出了全部质数。矛盾!
有限的“全部质数名单”不可能存在,所以质数有无穷多个。
这个论证适用于任意有限个质数,不是只验证了前几个例子。注意更强的说法“乘积加一一定是质数”并没有在证明中出现,也根本不需要它。
THINK 03 / 不要走错最后一步
区分“数本身是质数”和“含有新的质因数”。
查看完整答案
选 D。N 可能是质数,也可能是合数。无论哪种情况,它必有质因数,且任何已列出的 pᵢ 都不能整除 N。
04 / EXPERIMENT / CHECK A FINITE LIST
最妙的反例:新造出的数,竟然是合数。
选取最前面的 k 个质数,让机器计算它们的乘积加一,再尝试分解质因数。把 k 调到 6,你会发现新造出的 30031 并不是质数。
演示只选取前 1 到 8 个质数,因此只是有限样例。对这些范围内的 N 使用精确整数运算和试除法分解;无限性结论由上面的通用证明保证,而不是由互动样例保证。
“把前几个质数相乘加一,得到的总是另一个质数”是错误的。30031=59×509 就是反例。但这完全不会损害欧几里得的证明,因为只要这个数有某个新的质因数,就足以推翻完整名单。
05 / YOUR TURN
如果换一种名单,证明还成立吗?
练习一 · 如果名单只有 3、5、7,可以怎样构造遗漏的质数?
计算 3×5×7+1=106=2×53。它不能被 3、5、7 整除,却含有质因数 2 和 53。这里说明“无论给出哪一张有限质数名单”,都能构造一个具有名单外质因数的数,不要求名单从 2 开始。
练习二 · 证明中为什么不能说“N 一定是质数”?
反例 N=2×3×5×7×11×13+1=30031=59×509 是合数。我们需要的只是“N>1,因此存在一个质因数”,并用余 1 的性质证明这个因数不在假设的完整清单里。
进阶挑战 · 假设已经有无限多个质数,能推出它们在整数里占固定比例吗?
不能。质数无穷多个只说明对任何界限都存在更大的质数,并不告诉我们它们有多密集。素数定理进一步说明不大于 x 的质数个数 π(x) 约为 x/log x,所以质数在正整数里的比例趋向 0,同时总数量仍无限增长。
数学证明有时不是寻找最后一个答案,而是证明“最后一个答案”根本不可能存在。