吳啟

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

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

一、歐幾里得的證明方法

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

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

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

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

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

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

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

所以 p 是一個(gè)新的素?cái)?shù)，

所以假設(shè)不正確，因此素?cái)?shù)有無窮多個(gè).

二、埃爾米特的證明方法

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

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

便只需證明必存在大于 n 的素?cái)?shù)即可.

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

若為 P 素?cái)?shù)，則結(jié)論成立；

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

i 都不能整除 P ，

則必存在一個(gè)比 n 大的素?cái)?shù) m ，有 m∣P .

因此素?cái)?shù)有無窮多個(gè).

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

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

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

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

考慮如下遞推式：

F0F1F2…Fn - 1 =∏k = 0

n - 1

Fk = Fn - 2（n ≥ 1）.

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

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

則當(dāng) n= 1 時(shí)，

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

（2）當(dāng) n ≥ 2 時(shí)， ∏Fk? = Fn ·∏Fk? = Fn （Fn? - 2） =（22n? + 1）·（22n? - 1） = 22n + 1? - 1 = Fn + 1? - 2 也成立.

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

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

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

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

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

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

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

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

同理， 因?yàn)椋∟2 ，N2? + 1） = 1 ，

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

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

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

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

因?yàn)椋∟k ，Nk? + 1） = 1 ，

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

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

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

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

由數(shù)學(xué)歸納法可知，素?cái)?shù)有無窮多個(gè).

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