喜欢本人文字的读者
>>> 欢迎选购本站电子书 <<<

素数有无穷多个之九类证明

- 卢昌海 -

0. 引言

素数 (prime number) 是除去 1 和本身之外不存在其他因子的大于 1 的正整数。 单纯从这个定义看， 素数没什么先验的理由必须有无穷多个， 然而对数学家来说， 很幸运的是： 素数有无穷多个。

有关这一命题的最早书面证明出现于公元前 300 年左右， 有 “几何之父” (father of geometry) 美誉的古希腊数学家欧几里得 (Euclid) 在《几何原本》 (Elements) 中陈述了这一命题并给出了证明 (列于《几何原本》第 9 卷的第 20 个命题)， 这一命题也因此被称为了 “欧几里得定理” (Euclid's theorem) 或 “欧几里得第二定理” (Euclid's second theorem)， 后者是由于《几何原本》第 7 卷的第 30 个命题——即一个素数若整除两个整数之乘积， 则至少整除两者之一——有时被称为 “欧几里得第一定理” (Euclid's first theorem)， 素数有无穷多个相应地被挤成 “老二”。

素数有无穷多个这一命题简单却魅力无穷， 且牵涉甚广， 故自欧几里得以来的 2,300 多年间， 后世数学家们又给出了数以百计的新证明。 那些新证明繁简不一， 且很多只是互为变种， 在本文中， 我们挑其中有代表性的九类证明略作介绍， 以飨读者。

1. 欧几里得的证明

首先当然是欧几里得的证明——虽然由于《几何原本》既是欧几里得本人的著作， 又是前人成就之汇集， 很难确切知晓该证明是来自前人还是欧几里得自创 (只能说并无前者的直接证据)。 欧几里得的证明已进入初等数学课堂， 因而几乎已是所有读者烂熟于胸的， 但知识意义上的平凡掩不去它的美。 英国数学家哈代 (G. H. Hardy) 在《一位数学家的辩白》 (A Mathematician's Apology) 一书中称这一证明历久弥新， 依然如初发现时一样重要， 两千年的时光不曾刻下丝毫褶痕。

当然， “不曾刻下丝毫褶痕” 是有所夸张的， 比如欧几里得对素数有无穷多个的表述是 “素数比任何指定个数的素数更多”， 证明过程采用了几何术语 (其中的 “数” 是用线段长度来表示的)， “指定个数” 则被选为了 3 个， 而不像现代证明中那样用一个代表任意数目的字母来表示， 以示普遍。 不过跟 “两千年的时光” 相比， 这些措辞习惯上的 “褶痕” 实是微不足道的， 证明的本质——即证明已知素数的连乘积加 1 是新素数或以新素数为因子——则无需丝毫改变。

欧几里得的证明通常被视为归谬法 (reductio ad absurdum) 的范例， 这种方法曾被哈代称为 “数学家最好的武器之一”， 并被比喻为国际象棋中的 “弃子开局法” (gambit)。 所不同的是——哈代补充说， 棋手只能牺牲个别棋子， 数学家却敢于假设整个游戏的失败——即假设所要证明的命题不成立。

不过， 归谬法虽得到哈代的力挺， 却不是所有数学家都认可的。 比如数学基础研究中的一个名为直觉主义 (intuitionism) 的流派就并不承认归谬法^[注一]。 但另一方面， 欧几里得的证明并非单纯的归谬证明， 而是同时给出了算法， 一种通过已知素数的连乘积加 1 所含的素因子构造新素数的算法^[注二]。 事实上， 在欧几里得的原始表述中， 算法的意味要明显强于归谬的意味， 从这点上讲， 欧几里得的证明与其说是归谬证明， 不如说是构造性证明 (constructive proof)， 而构造性证明是连直觉主义这种在丢弃数学成果方面最大刀阔斧的流派也认可的。 因此， 欧几里得的证明尽管既古老又简单， 同时却是极其强大的。

在后世数学家给出的新证明中， 有很多是欧几里得证明的变种。 比如德国数学家库默尔 (Ernst Kummer) 于 1878 年， 荷兰数学家斯蒂尔杰斯 (Thomas Stieltjes) 于 1890 年， 分别给出了这样的变种： 假设只存在有限多个素数 p₁, ..., p_n， 令 N = p₁···p_n， 则所有 p_i (i = 1, ..., n) 都是 N 的素因子。 由于 p₁, ..., p_n 是全部素数， 其中必有一个是 N — 1 的素因子， 设其为 p_r (1 ≤ r ≤ n)， 则 p_r 同时是 N 与 N — 1 的素因子， 从而也是两者之差——也就是 1——的素因子。 由于这是不可能的， 故素数有无穷多个。 读者想必看出了， 这只是将欧几里得证明中的连乘积加 1 改为减 1， 优美度甚至稍逊 (因原则上需对连乘积减 1 等于 1 的简单情形作出附加说明)。 如此平庸的变种得以冠名而流传， 有些出人意料。

另一个据说是法国数学家埃尔米特 (Charles Hermite) 给出的变种在新意上略胜于前一变种， 具体是这样的： n! + 1 的素因子必定大于 n (否则被 n! + 1 除余 1， 不可能是素因子)， 由于 n 是任意的， 因而无论已找到多少素数， 都还可以找到更大的， 故素数有无穷多个。

2. 利用互素序列的证明

所有将一串整数乘起来再做点加减法的证明， 在很大程度上都是欧几里得证明的变种， 接下来要介绍的则是一些与欧几里得证明有着不同思路或视角的证明。 其中第一类是利用所谓互素序列 (series of mutually prime integers) 的证明。 这类证明的思路很简单： 假如能找到一个无穷序列， 其中任意两项都是互素的 (即所谓互素序列)， 那就等于证明了素数有无穷多个——因为每一项的素因子都彼此不同， 项数无穷， 素因子的个数——从而素数的个数——自然也就无穷。

因此问题归结为： 什么样的序列既是无穷序列又是互素序列？

1730 年， 德国数学家哥德巴赫 (Christian Goldbach) 在给著名数学家欧拉 (Leonhard Euler) 的一封信里给出了一个合乎需要的互素序列： F_n = 2²ⁿ + 1 (n = 0, 1, ...)， 并由此证明了素数有无穷多个。 有些读者想必认出来了， 这个互素序列里的各项是 17 世纪的法国数学家费马 (Pierre de Fermat) 引进的所谓的费马数 (Fermat's number)。 费马曾经猜测， 所有费马数都是素数， 他并且验证了 n = 0, 1, 2, 3, 4 的情形， 全都符合猜测。 由于费马数随 n 增长极快， 在没有计算机的时代， 对更大的 n 进行验证极其繁琐， 费马的猜测因此陷入不了之局长达近百年。 不过到了 1732 年， 欧拉证明了 F₅ = 641 × 6700417 不是素数， 从而推翻了费马的猜测。 自那之后， 截至 2014 年， 人们又陆续证明了从 F₆ 到 F₃₂ 的所有费马数都不是素数， 这期间有人反费马而行之， 猜测除有限多个外， 费马数全都不是素数。 直到今天， 费马数里究竟有多少素数， 多少非素数， 依然是个谜^[注三]。

不过费马的猜测虽不成立， 即费马数并非全是素数， 却可以证明所有费马数彼此互素， 因为费马数满足这样一个关系式： F_n — 2 = F₀F₁···F_n—1^[注四]。 这关系式表明 F₀, ..., F_n—1 全都可以整除 F_n — 2， 从而也意味着 F₀, ..., F_n—1 的所有素因子都可以整除 F_n — 2。 假如这些素因子中有任何一个可以整除 F_n， 则该素因子就可以整除 F_n 和 F_n — 2 之差——也就是 2， 而这是不可能的 (因为能整除 2 的素因子只有 2， 但 F_n 全都是奇数)。 因此 F_n 不跟 F₀, ..., F_n—1 共享任何素因子， 从而意味着所有费马数彼此互素。

这里可以补充的是： 在哥德巴赫给出对素数有无穷多个的这一新证明时， 费马关于所有费马数都是素数的猜测尚未被欧拉推翻， 假如费马的猜测成立， 哥德巴赫的证明就多此一举了——因为费马数本身就直接给出了无穷多个素数。 不过猜测毕竟是猜测， 哥德巴赫自己就是提猜测的高手， 自然明白个中道理， 没把有能力证明的结论不必要地建立在别人的猜测之上。 哥德巴赫另辟蹊径利用的所有费马数彼此互素这一特点则被称为了哥德巴赫定理 (Goldbach's theorem)。

利用互素序列的证明也有很多变种， 差别仅在于选择不同的互素序列， 就不赘述了。

3. 利用素数分布的证明

比素数的个数更复杂的问题是素数的分布。 由于素数有无穷多个是欧几里得时代就已证明了的结论， 虽不时有数学家提出新证明， 但跟研究素数的分布相比， 显然是后者更令人感兴趣， 更有难度， 研究的结果也更丰富多彩。

不难想到， 由素数的分布也可得到素数有无穷多个的结论， 事实正是如此。

比如法国数学家阿达马 (Jacques Hadamard) 和比利时数学家瓦莱-普森 (Charles Jean de la Vallée Poussin) 于 1896 年证明的素数定理 (Prime number theorem) 给出了 N 以内的素数个数 π(N) 的渐近分布为 π(N) ~ N/ln(N)。 由于 N/ln(N) 随 N 趋于无穷， 素数定理显然直接蕴含了素数有无穷多个的结论。 不过素数定理是一个证明相当复杂的定理， 哪怕所谓的 “初等证明” (elementary proof) 也非同小可。 最早给出 “初等证明” 的挪威数学家塞尔伯格 (Atle Selberg) 甚至在所获菲尔茨奖 (Fields Medal) 的获奖理由中都包含了 “初等证明”。 用素数定理来得到素数有无穷多个的结论无疑是 “牛刀杀鸡”， 并且大可不必。

因为由一些比素数定理简单得多——当然也弱得多——的素数分布定理也能得到素数有无穷多个的结论。

比如 1850 年， 俄国数学家切比雪夫 (Pafnuty Chebyshev) 证明了法国数学家伯特兰 (Joseph Bertrand) 提出的所谓伯特兰假设 (Bertrand's Postulate)， 即对任意正整数 n ≥ 2， 至少存在一个素数 p 使得 n < p < 2n。 1932 年， 匈牙利数学家埃尔德什 (Paul Erdös) 给出了已升级为伯特兰-切比雪夫定理 (Bertrand–Chebyshev theorem) 的伯特兰假设的初等证明^[注五]。 利用伯特兰假设显然也立刻就能得到素数有无穷多个的结论。

由上述两个证明不难推想到， 利用素数分布证明素数有无穷多个的途径是很多的。 几乎可以这么说， 有关素数分布的定理有多少， 相应的证明也就有多少 (因为任何素数分布定理， 如果连素数有无穷多个都得不出， 实在是有愧于 “素数分布定理” 这一光荣称号的)。 不仅如此， 就连欧几里得证明的某些变种也可轻易改写为利用素数分布的证明， 比如上文提到的埃尔米特的变种就相当于给出并利用了这样一个有关素数分布的定理： 对任意正整数 n ≥ 2， 在 n 与 n! + 1 之间 (含 n! + 1 本身) 至少存在一个素数。

4. 利用代数数论的证明

数学犹如一棵大树， 数论乃是一个分支， 本身又包含若干分支， 代数数论和解析数论便是其中两个。 这两个分支对证明素数有无穷多个也各有手段， 值得分别作一个简单介绍。

利用代数数论手段证明素数有无穷多个的出发点之一是利用所谓的欧拉 φ 函数 (Euler's phi function)。 对任一正整数 n， 欧拉 φ 函数的取值 φ(n) 定义为：

φ(n) := 不大于 n 且与 n 互素的正整数的个数

或者用符号表示为 (a 为正整数)：

φ(n) := ‖{a | 1 ≤ a ≤ n; gcd(a, n) = 1}‖

其中 gcd(a, n) 表示 a 和 n 的最大公约数 (greatest common divisor)， ‖{...}‖ 表示集合 {...} 的元素个数。

这个函数是欧拉于 1763 年提出的， 德国数学家高斯在 1801 年出版的《算术研究》 (Disquisitiones Arithmeticae) 一书中以 φ 表示之， 故而得名。 除这一名称外， 1879 年， 英国数学家西尔维斯特 (James Sylvester) 用源自拉丁文， 含义为 “这么多” 的 “totient” 一词表示这一函数 (因这一函数给出的是： 对任一正整数 n， 总计有 “这么多” 个不大于 n 的正整数与之互素)， 受之影响， 欧拉 φ 函数有时也被称为 Euler's totient function， 中文译为欧拉总计函数。 为了对欧拉 φ 函数有一个直观了解， 读者可对最小的 n 验证一下欧拉 φ 函数的取值， 比如 φ(2) = 1， φ(3) = 2， φ(4) = 2， φ(5) = 4， φ(6) = 2， 等等。

细心的读者也许会抱怨： 在上述定义及说明中， 明明是只见数论不见 “代数” 嘛！ 这是由于我们只对证明素数有无穷多个感兴趣， 为免生枝节， 免作不必要的概念铺垫， 刻意回避了代数色彩。 对于想见 “代数” 一面的读者， 欧拉 φ 函数可以这样来定义： 对任一正整数 n， φ(n) 给出的是环 ℤ/nℤ 中的可逆元 (invertible element) 的数目。

接下来我们直奔主题， 介绍对素数有无穷多个的证明。

这个证明需要用到欧拉 φ 函数的几个简单性质。

首先是对任一素数 p， φ(p) = p — 1， 这是因为 1, ..., p — 1 这 p — 1 个不大于 p 的正整数显然都跟 p 互素。

其次是对两个不同——从而当然互素——的素数 p₁ 和 p₂， φ(p₁p₂) = (p₁ — 1)(p₂ — 1)， 这是因为从 1 到 p₁p₂ 这 p₁p₂ 个正整数中， p₁, 2p₁, ..., p₂p₁ 这 p₂ 个正整数跟 p₁p₂ 有共同素因子 p₁； p₂, 2p₂, ..., p₁p₂ 这 p₁ 个正整数跟 p₁p₂ 有共同素因子 p₂； 其余全都跟 p₁p₂ 互素。 由此得到 φ(p₁p₂) 为 p₁p₂ — p₂ — p₁。 但其中 p₁p₂ 被重复计算了一次， 因此要补回一个 1， 由此得到 φ(p₁p₂) = p₁p₂ — p₂ — p₁ + 1 = (p₁ — 1)(p₂ — 1)^[注六]。

上述第二个性质显然可以推广为针对任意多个彼此不同——从而当然彼此互素——的素数 p₁, ..., p_n， 即 φ(p₁···p_n) = (p₁ — 1)···(p_n — 1)。 很明显， 对所有 n ≥ 2， 连乘积 (p₁ — 1)···(p_n — 1) 中至多有一项是 1 (对应于 p_i = 2)， 其余皆不小于 2， 乘积当然也不小于 2， 即 φ(p₁···p_n) ≥ 2。 这说明在 1 与 p₁···p_n 之间至少有两个正整数与 p₁···p_n 互素， 两个中的一个显然是 1， 另一个则不小于 2 且不能以 p₁, ..., p_n 中的任何一个为素因子 (否则不可能跟 p₁···p_n 互素)。 从而其素因子 (可以是它自身) 必然是 p₁, ..., p_n 之外的新素数。

上述推理可无穷重复， 从而表明素数有无穷多个。

上述证明虽名为 “利用代数数论的证明”， 代数味其实很淡。 利用代数数论的证明还有代数味更浓的， 直接用到戴德金整环 (Dedekind domain)、 素理想 (prime ideal) 之类如假包换的代数数论概念， 由于需作较多的概念铺垫， 就不介绍了， 只弱弱地提醒一句： 这类证明并非独木桥。

5. 利用解析数论的证明

…… 详见全文 ……

6. 组合证明

…… 详见全文 ……

7. 拓扑证明

…… 详见全文 ……

8. 信息证明

…… 详见全文 ……

9. 其他证明

…… 详见全文 ……

10. 结语

…… 详见全文 ……

本文已收录于电子书《数学杂谈》
以上预览约为本文内容之 40%
欲读剩余部分
>>>>>> 请购买该书 <<<<<<

注释

1. 直觉主义直接反对的是所谓排中律 (law of excluded middle)， 归谬法的不被承认是其副产品。 另外顺便说一下， 有一种 “精分” 的看法主张对归谬法和反证法 (proof by contradiction) 作出区分， 前者意在反驳 (即 “归谬”)， 后者意在证明 (即 “反证”)， 且前者之 “谬” 不限于逻辑， 后者则只限于用逻辑矛盾完成证明。 从这一区分上讲， 欧几里得的证明偏于反证而非归谬。 不过此处引述的哈代称之为归谬法， 本文就不予 “精分” 了。
2. 如果从最小的素数 2 出发， 只用这种算法寻找新素数， 且每次只找最小的素因子， 由此得到的素数序列被称为欧几里得-马林序列 (Euclid-Mullin sequence)——因美国数学家马林 (Albert A. Mullin) 对其的研究而得名。 欧几里得-马林序列目前只算出了前几十项 (因计算量随项数增加太快)， 大小则剧烈起伏 (比如前 10 项分别为： 2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139)。 是否所有素数都会出现在欧几里得-马林序列中？ 这是一个迄今尚未解决的问题。
3. 从基于概率的所谓 “概率启发式理由” (probabilistic heuristic justification) 出发， 可推测费马数中的素数个数是有限的。 因为 N 附近的素数分布概率为 A/ln(N) (A 为常数)， 因此费马数中素数总数的期望值为 Σ_n[A/ln(F_n)] ~ AΣ_n(2^—n) ≲ A， 是有限的。 不过 “概率启发式理由” 假定了费马数是素数的概率跟一个普通正整数是素数的概率一样， 没有任何特殊性， 这一点有迹象显示未必成立， 因此这一理由至多只是 “启发式” 的。
4. 这一关系式的证明很容易， 感兴趣的读者请用数学归纳法试试。
5. 对这一证明感兴趣的读者请参阅拙作 Bertrand 假设。
6. 这一结果也可表述为 φ(p₁p₂) = φ(p₁)φ(p₂)， 且可推广为： 若 m 和 n 互素， 则 φ(mn) = φ(m)φ(n)， 这一推广的证明与 φ(p₁p₂) = φ(p₁)φ(p₂) 的证明相近， 只需对 m 和 n 的素数分解式作出类似分析。
7. 当然， 这只是启发性的思路， 严格的证明必须考虑收敛性等因素， 可参阅拙作《黎曼猜想漫谈》的 附录一。
8. 当然， 欧拉乘积公式并不能直接用于 s = 1， 因此这也只是启发性的思路， 需以适当的极限语言严格化， 这个就留给读者去做吧。 另外可以补充的是， 利用欧拉乘积公式不仅能得出素数有无穷多个， 而且可对素数分布作出一个定性上等同于素数定理的估计， 感兴趣的读者可参阅拙作《黎曼猜想漫谈》的 第三章。
9. ℤ 是整数集， aℤ + b 是所有形如 a 的整数倍加上 b 的整数组成的集合， 也就是 {an + b | n ∈ ℤ}。
10. 对于我们所面对的情形， 这可以简单证明如下 (请注意证明所用的是二进制)： 假设位数为 n 的所有正整数在上述编码下是纯压缩的， 且至少压缩掉两位， 则相应的编码长度为 1, ..., n—2。 具有这种长度的编码总共有 2¹ + ... + 2^n—2 = 2^n—1 — 2 种。 另一方面， 位数为 n 的正整数总共有 2^n—1 个 (注意位数为 n 的正整数的首位必须是 1， 否则实际位数会小于 n， 因此只有后 n — 1 位的数字可在 0 和 1 之间任选， 共有2^n—1 个)。 将 2^n—1 个正整数压缩成 2^n—1 — 2 种编码， 其中必然有不同的正整数被压缩成相同的编码， 从而不可能是不损失信息的。
11. 不过要提醒读者注意的是， 这个组合证明虽号称是信息证明的改写， 却并非等价改写， 而只是实质相近。
12. 这也意味着以素数分解为基础的编码——也就是信息证明中的编码——是不可能不损失信息的 (当然前提是素数只有有限多个)。 读者想必还记得， 这正是 [注十] 中得出过的结论， 信息证明与组合证明的实质相近可见一斑。
13. 为周全起见， 此处可作一个补充说明： 如果注意到 1 + 2Π_p'p' 不可能被任何一个 p 整除， 本证明可直接转为欧几里得证明的变种； 但如果不利用 1 + 2Π_p'p' 的特殊性质， 直接套用归谬前提， 本证明则可视为不同类型的证明。
14. 当然， 阿蒂亚与辛格证明的其实是一系列指标定理， 从而不完全等同于对单一定理的反复证明， 不过阿蒂亚的回答对单一定理的反复证明也有所涵盖。

2018 年  8 月 13 日完稿
2018 年  8 月 14 日发布
https://www.changhai.org/

站长往年同日 (8 月 14 日) 发表的作品

• 2008-08-14： 眩目的八月 (上)

站长近期发表的作品

• 2024-05-09： 短视频文字脚本 (2024.04)
• 2024-05-02： 微言小义 (2024.04)
• 2024-04-21： 一段爱因斯坦的原始录像
• 2024-04-16： 关于我的 YouTube 频道
• 2024-04-12： 物理学家问 “上帝”

网友讨论选录

• 新浪博友： 万精油微博   (发表于 2018-08-16)

  从前读鲁迅的孔乙己， 记得最清楚的有两句话： “读书人窃书不为偷”， “茴香豆的茴字有四种写法”。 这个素数有无限个的九种证明算是数学家写茴字， 九种写法 (其实还不止)。 很好的科普， 转。

• 网友： 往事如昨   (发表于 2018-08-17)

  我发现我还没有 2000 多年前的人聪明。

• 卢昌海   (发表于 2018-08-17)

  我在 2016-10-23 的微博中提到， 现代社会的人道主义、 平等等意识基本终止了原始意义上的进化， 更何况 2000 年对于进化来说是极短的时间。 因此现代人平均而言不比古希腊先贤更智慧是不足为奇的。 现代社会的进化主要通过教育， 但普通人从中学到的可能多为知识， 未必是智慧。

• 网友： 宇澄   (发表于 2018-08-18)

  不久前读过 Scientific Americans 杂志的一篇文章， 里面谈到从生物学的角度看， 人类仍然是在不断进化， 里面特别提到了最近 3 万年人类进化得最显著的是出现黑直头发、 蓝眼睛、 耐乳糖。

  至于人是不是进化得比 2000 年前聪明了， 我想大势来说应该是的， 只要看看聪明的人是不是有更多的生存繁衍机会， 有的话答案就应该是人类变聪明了。

  接下来就得说些政治不正确的话了。 犹太人和祖先被贩卖到美洲当奴隶的黑人都是颠沛流离的民族， 犹太人靠聪明求得生存， 不然就被灭掉。 相比之下黑人则由奴隶主挑选身强力壮不大聪明的才容易生存。 我想假如犹太人跟黑人的历史命运调过来， 那现在出现的情形就会是犹太人包办 100 米跑冠军而黑人狂拿诺贝尔奖。 我想卢兄在 2018-07-17 的微博中提到过的小平邦彦有关人类进化成电脑般精于计算的设想大概也是这意思吧？

  由于二战纳粹德国的教训， 加上人权宣言等等， 照顾弱势群体已经成为了人类的普世价值观， 这是人类思想进步文明的象征。 另一方面， 优生学被指责为助纣为劣的邪门东西， 这样的结果是会降慢人类在某些方面进化的速度的。

• 卢昌海   (发表于 2018-08-18)

  宇澄兄所说亦有道理， 尤其是在战乱等残酷年代及草菅人命的地方， 类似原始丛林的生存竞争依然存在， 以两千年的历史观之更是如此， 其比例只在近代才开始减小。

本文的讨论期限已过， 如果您仍想讨论本文，
请在每个月前七天的 “读者周” 期间前来讨论。

>> 查阅目前尚在讨论期限内的文章 <<