素数有无穷多个？

吴启

素数又称为质数，其定义是在大于1的自然数中， 除了1和它本身以外不再有其他因数的自然数；否则 称为合数.素数和合数是一组相对的概念（规定1既不 是素数也不是合数）.人类在很早的时候就开始研究素 数了，神秘的素数令无数数学家为之魂牵梦绕.在数学 中就有一门分支学科专门研究素数（整数）及其性质， 称为数论.你一定听过我国数学家陈景润攻克哥德巴 赫猜想的故事吧，讲的就是这个.素数从2开始，后续 有3、5、7、11等，你是否有这样的疑问：假如素数可数， 是否可以数完？换句话说，素数是有限个的，还是无穷 的？

答案是无穷多个的.我们首先来了解一下算术基 本定理：设 n 为一个大于1的自然数，则有 n = p1 p2…ps ， 其中 s 为某自然数，pj （1 ≤ j ≤ s） 是素数，并且在不记素 数排列次序的意义下，上式分解是唯一的.

一、欧几里得的证明方法

关于素数有无穷多个的证明，早期经典的证明是 欧几里得（Euclid，约公元前330年—公元前275年）在 《几何原本》中的证明.

欧几里得用到了数学中的反证法：

假设 p1，p2， … ，pr  全都是素数，且 p1

令 P =p1p2 …pr+1 ，并且 p 为 P 的一个素因数 ，

则 p ≠pi （1 ≤ i ≤ r） ，

否则 p∣P 且 p∣（P - 1） （ p 整除 P ，且 p 整除 P - 1），

从而 p∣[P -（P - 1）] ，即 p∣1，这是不可能的.

所以 p 是一个新的素数，

所以假设不正确，因此素数有无穷多个.

二、埃尔米特的证明方法

第二个证明来自法国数学家埃尔米特（Hermite， 1822年— 1901年），他的证明过程也是非常简洁优美.

埃尔米特考虑到任意的正整数 n ，

便只需证明必存在大于 n 的素数即可.

构造 P = n！+1，

若为 P 素数，则结论成立；

若 P 为合数，对于任意的正整数 i（1 ≤ i ≤ n） ，

i 都不能整除 P ，

则必存在一个比 n 大的素数 m ，有 m∣P .

因此素数有无穷多个.

三、利用费马数证明

另一个证明来源于数学史上一个著名的乌龙事 件，数学家费马发现，对于 Fn = 22n + 1（n = 0，1，2，…） ，前 五个数均为素数，于是他猜想所有的都是素数，费马 没 给 出 证 明 ，但 欧 拉 发 现 F5 =4294967297=641 × 6700417是一个合数，直接无情地推翻了费马的猜想.

利用费马数证明素数无限可以遵循如下思路：证 明费马数两两互素?每个费马数都有其独特的素因 数（费马素数的素因数即是它本身）?无限的费马数 对应无限的素数.

后面两步比较好理解，现在只需证明的是费马数 两两互素.

考虑如下递推式：

F0F1F2…Fn - 1 =∏k = 0

n - 1

Fk = Fn - 2（n ≥ 1）.

对于上述递推关系的证明，可以简单地用数学归纳法证明：

（1）易知 F0 = 3 ， F1 = 5 ，

则当 n= 1 时，

有F1  - 2 = 2 = ∏Fk  = F0 成立；

（2）当 n ≥ 2 时， ∏Fk  = Fn ·∏Fk  = Fn （Fn  - 2） =（22n  + 1）·（22n  - 1） = 22n + 1  - 1 = Fn + 1  - 2 也成立.

事 实 上 ，对 于 任 意 两 个 不 同 的 费 马 数 Fk   和 Fn （k < n） ，则由递推关系可知Fn  ≡ 2（mod Fk） ，

继而由辗转相除法可知gcd（Fn ， Fk） = gcd（Fk ， 2） ，

但由于所有的费马数均为奇数，所以gcd（Fk ， 2） = 1 ， 即任意两个费马数互素，证明完毕.

四、数学归纳法

最后一个证明方法是数学归纳法，非常巧妙.

任取素数 N1  ，则有（N1 ，N1  + 1） = 1 ， 即 N1  与 N1  + 1 互 素，因此 N1  + 1 的素因数中，至少存在 1 个不等于 N1 的素因数 m1  .

令 N2  = N1 （N1  + 1） ，

则 N2   的素因数中，存在 2 个互不相等的素因数 N1  ， m1  .

同理， 因为（N2 ，N2  + 1） = 1 ，

因此 N2  + 1 的素因数中，至少存在 1 个不等于 N1 和 m1  的素因数 m2  .

令 N3  = N2 （N2  + 1） ，

则 N3   的素因数中，存在 3 个互不相等的素因救 N1 ， m1 ， m2   ，

假设 N 至少有 k 个互不相等的素因数，

因为（Nk ，Nk  + 1） = 1 ，

因此 Nk  + 1 的素因数中，

至少存在1个不等于N1 ， m1 ， m2 ， …，mk - 1  的素因数 mk  ，

令 Nk  + 1 =Nk （Nk  + 1） ，

则 Nk  + 1 的素因数中，存在 k +1 个互不相等的素 因救 N1 ， m1 ， m2 ， …， mk  .

由数学归纳法可知，素数有无穷多个.

自从欧几里得发表他的证明方法以来，2000 多年 过去了，人们已经找到了其他方法来证明存在无穷多 个素数.其中一些是重申欧几里得方法的巧妙，还有一些利用了欧几里得时代不存在的数学新分支.