天下素數有多少

歐幾里德 (Euclid 約前325 - 約前265)

(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )

 

素數有多少

到底素數 (Prime Number) 有多少個?

我們研究素數的,一開始便會這一條問題。

原來早在公元前二三百年,古希臘數學先進歐幾里德 (Euclid 約前325 - 約前265) 已給出答案和證明 (Proof)。答案是無限個之多,證明不難,只用了一個技巧「反證法」(Proof by Contradiction)。

反證法是指先假設命題錯誤,再去推演,得出與事實相矛盾的結果,從而推翻開始的假設,即命題是正確了。

 

我們不妨假設素數有有限的 n 個而已,我們順序由小至大,以 p1、 p2、 p3、 ... 、 pn 表示所有素數。

考慮一數 N = p1*p2*p3*...*pn+1,N 是合數 (Composite Number),還是素數?

若 N 是素數便和有限個素數的假設相矛盾。故 N 是合數,但 N 不是 p1、 p2、 p3、 ... 、 pn 的倍數,則 N 必含有其他素因子,這亦產生矛盾。所以先前假設素數個數是有限的是不對,即素數有無窮多個。

 

4k-1 的也無限

我們亦可用相類似手法證明型如 4k-1 和 6k-1 的素數個數有無限個之多。

設型如 4k-1 的素數只得有限的 n 個,我們順序由小至大,以 p1、 p2、 p3、 ... 、 pn 表示該類素數。

我們考慮 N = 4*p1*p2*p3*...*pn - 1,N 是型如 4k-1 的數,它不是素數,因這與假設矛盾。故 N 是合數。

但 N 的素因子不會單是 4k+1 型的素數,因 (4k1+1)*(4k2+1) = 16k1k2+4k1+4k2+1 = 4r+1 。故全是 4k+1 型的素數的乘積必是 4k+1 型的數。即 N 含有起碼一個型如 4k-1 的素因子,但這素因子不會是 p1、 p2、 p3、 ... 、 pn ,因而產生矛盾。所以型如 4k-1 的素數也是有無限個之多。

 

除了 2 和 3 以外,其他的素數一是屬於 6k+1 型,一是屬於 6k-1 型,我們亦可利用上法證明 6k-1 型的素數有無限個之多。證明則留給閣自己試試吧。

證明素數有無限個是不難,但證明其他類型的素數的個數是否也是無限個則不易。

但這一方法不可用於型如 4k+1 和 6k+1 的素數個數上,因為上述兩類數的素因子不一定屬於本類。如 21 = 3*7,3、7均是 4k-1型,但 21 卻是 4k+1型的。又如 55 = 5*11 ,5、11均是 6k-1型,但 55 卻是 6k+1型的。

 

另外從歐幾里德的證明方法也引申三種新類別的素數,詳見另文《歐幾里德引來的素數》,相信這歐幾里德本人也永遠想不到。

 

草答數論問題

拜讀潘承洞 (Chengdong Pan 1934-1997) 和潘承彪 (Chengbiao Pan 1938- ) 兄弟合著的《初等數論(第二版)》,此書初版於1992付印,為一較有系統的初等數論 (Elementary Number Theory) 讀物,十年後二版的修訂補充了一些新課題和例子,然而當時潘承洞已離人世,修訂的工作只有潘承彪一人來完成,可謂有點人面桃花之感。

草答的「草」有兩重含意,一是本人幼時的別名含有「草」字,二是這回答真的有一點「草草了事」:既沒有完整步驟,也不是全用數學語言表示,還請見諒。往下兩個證明原是書中的兩道練習題,「草」人「草」證於此,若有不善,煩望賜教。

 

1. 設 n 為非負整數,Fn = 2^(2n) +1,即費馬數 (Fermat Number) 。再設 m 不等於 n 。證明若 d > 1 且 d 整除 Fn ,則 d 不整除 Fm 。由此推論素數有無限多個。(原書頁13題17)

證:

若 d整除 Fn ,則存在一整數 (Integer) k 使 Fn = 2^(2n) +1 = dk ,即 2^(2n) = dk-1

因 m 不等於 n ,故設 m=n+a, Fm = 2^(2m) +1 = 2^(2n+a) +1 = 2^(2n *2a) +1 = [2^(2n)]^2a+1

即 Fm = (dk-1)^(2a) +1

把上式展開,Fm = d 的倍數 +1+1 = d 的倍數 + 2 。若要 Fm 同被 d 整除,則只有 d = 2 ,但所有費馬數均為奇數 (Odd Number),故不可能有 2 這個素因子,所以不同的費馬數有不同的素因子。由於費馬數個數無限,故素數個數也無限。

(註:這證明最先由哥德巴赫 (Christian Goldbach 1690-1764) 1730年 7月給歐拉 (Leonhard Euler 1707-1783) 的信中提及,這也許是哥德巴赫寫出的唯一的證明。)

 

2. 設 n 為不少於 3 之整數。證明 n! - 1 的素因子 > n。由此推出素數個數無窮多,並求出最小的 n 使 n! - 1 不是素數。

證:

因為 2、3、...、n 整除 n! ,故它們不整除 n! - 1,所以 n! - 1 的素因子必大於 n 。由於 n可以是任何整數,故存在大於任何整數之素數,即素數個數是無限。而最小的 n 使 n! - 1 不是素數為 n = 5,即 n! - 1 = 119 = 7 * 17。(註:考慮 n! + 1,亦有異曲同工之妙,詳見另文《歐幾里德引來的素數》。)

 

參考文獻及網址:

Ribenboim, P. 'The Little Book of Bigger Prime' , New York: Springer-Verlag, 1991.

潘承洞;潘承彪  初等數論(第二版), 北京:北京大學出版社, p. 13, 2003