天下素數有多少
歐幾里德 (Euclid 約前325 - 約前265)
(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/
)
素數有多少
到底素數 (Prime Number) 有多少個？
我們研究素數的，一開始便會這一條問題。
原來早在公元前二三百年，古希臘數學先進歐幾里德 (Euclid 約前325 - 約前265) 已給出答案和証明。答案是無限個之多，証明不難，只用了一個技巧「反証法」。
反証法是指先假設命題錯誤，再去推演，得出與事實相矛盾的結果，從而推翻開始的假設，即命題是正確了。
我們不妨假設素數有有限的 n 個而已，我們順序由小至大，以 p1、 p2、
p3、 ... 、 pn 表示所有素數。
考慮一數 N = p1*p2*p3*...*pn+1，N
是合數 (Composite Number)，還是素數？
若 N 是素數便和有限個素數的假設相矛盾。故 N 是合數，但 N 不是 p1、 p2、
p3、 ... 、 pn 的倍數，則 N 必含有其他素因子 (Prime Divisor) ，這亦產業矛盾。所以先前假設素數個數是有限的是不對，即素數有無窮多個。
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
型的素數有無限個之多。証明則留給閣自己試試吧。
証明素數有無限個是不難，但証明其他類型的素數的個數是否也是無限個則不易。
另外從歐幾里德的証明方法也引申三種新類別的素數，詳見另文《歐幾里德引來的素數》，相信這歐幾里德本人也永遠想不到。
草答數論問題
拜讀潘承洞和潘承彪兄弟合著的《初等數論(第二版)》，此書初版於1992付印，為一較有系統的初等數論 (Elementary
Number Theory) 讀物，十年後二版的修訂補充了一些新課題和例子，然而當時潘承洞已離人世，修訂的工作只有潘承彪一人來完成，可謂有點人面桃花之感。
草答的「草」有兩重含意，一是本人幼時的別名含有「草」字，二是這回答真的有一點「草草了事」：既沒有完整步驟，也不是全用數學語言表示，還請見諒。往下兩個証明原是書中的兩道練習題，「草」人「草」証於此，若有不善，煩望賜教。
1. 設 n 為非負整數，Fn = 2^(2n) +1，即費馬數
(Fermat Number) 。再設 m 不等於 n 。証明若 d > 1 且 d 整除 Fn ，則 d 不整除 Fm
。由此推論素數有無限多個。(原書頁13題17)
証：
若 d整除 Fn ，則存在一整數 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 ，但所有費馬數均為奇數，故不可能有 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.
