素數(shù)有無窮多個？

吳啟

素數(shù)又稱為質(zhì)數(shù)，其定義是在大于1的自然數(shù)中， 除了1和它本身以外不再有其他因數(shù)的自然數(shù)；否則 稱為合數(shù).素數(shù)和合數(shù)是一組相對的概念（規(guī)定1既不 是素數(shù)也不是合數(shù)）.人類在很早的時候就開始研究素 數(shù)了，神秘的素數(shù)令無數(shù)數(shù)學(xué)家為之魂牽夢繞.在數(shù)學(xué) 中就有一門分支學(xué)科專門研究素數(shù)（整數(shù)）及其性質(zhì)， 稱為數(shù)論.你一定聽過我國數(shù)學(xué)家陳景潤攻克哥德巴 赫猜想的故事吧，講的就是這個.素數(shù)從2開始，后續(xù) 有3、5、7、11等，你是否有這樣的疑問：假如素數(shù)可數(shù)， 是否可以數(shù)完？換句話說，素數(shù)是有限個的，還是無窮 的？

答案是無窮多個的.我們首先來了解一下算術(shù)基 本定理：設(shè) n 為一個大于1的自然數(shù)，則有 n = p1 p2…ps ， 其中 s 為某自然數(shù)，pj （1 ≤ j ≤ s） 是素數(shù)，并且在不記素 數(shù)排列次序的意義下，上式分解是唯一的.

一、歐幾里得的證明方法

關(guān)于素數(shù)有無窮多個的證明，早期經(jīng)典的證明是 歐幾里得（Euclid，約公元前330年—公元前275年）在 《幾何原本》中的證明.

歐幾里得用到了數(shù)學(xué)中的反證法：

假設(shè) p1，p2， … ，pr? 全都是素數(shù)，且 p1

令 P =p1p2 …pr+1 ，并且 p 為 P 的一個素因數(shù) ，

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

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

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

所以 p 是一個新的素數(shù)，

所以假設(shè)不正確，因此素數(shù)有無窮多個.

二、埃爾米特的證明方法

第二個證明來自法國數(shù)學(xué)家埃爾米特（Hermite， 1822年— 1901年），他的證明過程也是非常簡潔優(yōu)美.

埃爾米特考慮到任意的正整數(shù) n ，

便只需證明必存在大于 n 的素數(shù)即可.

構(gòu)造 P = n！+1，

若為 P 素數(shù)，則結(jié)論成立；

若 P 為合數(shù)，對于任意的正整數(shù) i（1 ≤ i ≤ n） ，

i 都不能整除 P ，

則必存在一個比 n 大的素數(shù) m ，有 m∣P .

因此素數(shù)有無窮多個.

三、利用費馬數(shù)證明

另一個證明來源于數(shù)學(xué)史上一個著名的烏龍事 件，數(shù)學(xué)家費馬發(fā)現(xiàn)，對于 Fn = 22n + 1（n = 0，1，2，…） ，前 五個數(shù)均為素數(shù)，于是他猜想所有的都是素數(shù)，費馬 沒 給 出 證 明 ，但 歐 拉 發(fā) 現(xiàn) F5 =4294967297=641 × 6700417是一個合數(shù)，直接無情地推翻了費馬的猜想.

利用費馬數(shù)證明素數(shù)無限可以遵循如下思路：證 明費馬數(shù)兩兩互素?每個費馬數(shù)都有其獨特的素因 數(shù)（費馬素數(shù)的素因數(shù)即是它本身）?無限的費馬數(shù) 對應(yīng)無限的素數(shù).

后面兩步比較好理解，現(xiàn)在只需證明的是費馬數(shù) 兩兩互素.

考慮如下遞推式：

F0F1F2…Fn - 1 =∏k = 0

n - 1

Fk = Fn - 2（n ≥ 1）.

對于上述遞推關(guān)系的證明，可以簡單地用數(shù)學(xué)歸納法證明：

（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 也成立.

事 實 上 ，對 于 任 意 兩 個 不 同 的 費 馬 數(shù) Fk?? 和 Fn （k < n） ，則由遞推關(guān)系可知Fn? ≡ 2（mod Fk） ，

繼而由輾轉(zhuǎn)相除法可知gcd（Fn ， Fk） = gcd（Fk ， 2） ，

但由于所有的費馬數(shù)均為奇數(shù)，所以gcd（Fk ， 2） = 1 ， 即任意兩個費馬數(shù)互素，證明完畢.

四、數(shù)學(xué)歸納法

最后一個證明方法是數(shù)學(xué)歸納法，非常巧妙.

任取素數(shù) N1? ，則有（N1 ，N1? + 1） = 1 ， 即 N1? 與 N1? + 1 互 素，因此 N1? + 1 的素因數(shù)中，至少存在 1 個不等于 N1 的素因數(shù) m1? .

令 N2? = N1 （N1? + 1） ，

則 N2?? 的素因數(shù)中，存在 2 個互不相等的素因數(shù) N1? ， m1? .

同理， 因為（N2 ，N2? + 1） = 1 ，

因此 N2? + 1 的素因數(shù)中，至少存在 1 個不等于 N1 和 m1? 的素因數(shù) m2? .

令 N3? = N2 （N2? + 1） ，

則 N3?? 的素因數(shù)中，存在 3 個互不相等的素因救 N1 ， m1 ， m2?? ，

假設(shè) N 至少有 k 個互不相等的素因數(shù)，

因為（Nk ，Nk? + 1） = 1 ，

因此 Nk? + 1 的素因數(shù)中，

至少存在1個不等于N1 ， m1 ， m2 ， …，mk - 1? 的素因數(shù) mk? ，

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

則 Nk? + 1 的素因數(shù)中，存在 k +1 個互不相等的素 因救 N1 ， m1 ， m2 ， …， mk? .

由數(shù)學(xué)歸納法可知，素數(shù)有無窮多個.

自從歐幾里得發(fā)表他的證明方法以來，2000 多年 過去了，人們已經(jīng)找到了其他方法來證明存在無窮多 個素數(shù).其中一些是重申歐幾里得方法的巧妙，還有一些利用了歐幾里得時代不存在的數(shù)學(xué)新分支.