從費馬小定理談起

法國數學家費馬 (Pierre de Fermat 1601-1665)

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

 

自一封信開始

1640年 6月,法國數學大師費馬 (Pierre de Fermat 1601-1665) 在給梅森 (Marin Mersenne 1588-1648) 的信中提及若干事實,詳見《梅森素數》一文,其中:

若 p 為素數,則 2p - 2 能被 p 整除。這相當於 2p-1-1 能被 p 整除。

後來在 1640年 10月 18日,他給貝西 (Frenicle de Bessy 1605-1675) 的一封信中更指出他證明了:

若 p 為素數, a 與 p 互素,則 ap-1-1 能被 p 整除。

以同餘式 (Congruence Expression) 表示則是,

ap-1 = 1 (mod p)

這便是著名的費馬小定理 (Fermat's Little Theorem 或 Fermat's Lesser Theorem) ,或費馬同餘式 (Fermat's Congruence Expression)。被冠以「小」的名字只是為了和世紀難題費馬大定理 (Fermat's Last Theorem) 相分,不存在任何貶意。為了方便對費馬小定理作研究,數學家定義了費馬商 (Fermat Quotient):

若 p 不整除 a 或 b ,我們有

qp(ab) = qp(a) + qp(b)

qp(p+1) = -1;qp(p-1) = 1

 

據此,如果 n 與 a 互素,且不能整除 an-1- 1, 則 n 必不是素數,即是合數。但如果 n 能整除 an-1-1 又怎樣? n 是素數嗎?即是問費馬小定理的逆命題 (Converse of Fermat's Little Theorem) 是成立嗎?

西方很長的時間以為這費馬小定理的逆命題是成立的,對於 1 < n < 300 的驗證中,能整除 2n-1-1 的奇數 n 全是素數,即大大支持了成立逆命題。附帶一言,以 a = 2 的費馬小定理逆命題,亦被稱為中國假設 (Chinese Hypothesis),但這似乎是西方人對中國古代數學的過分推崇而已,此命題和中國似乎連不上任何關係。普魯士數學家哥德巴赫 (Christian Goldbach 1690-1764) 在其寄給歐拉 (Leonhard Euler 1707-1783) 的信中還表示他會嘗試證明這逆命題。結果如何,他自然是失敗而回。在 1819年,法國數學家賽路斯 (Sarrus) 找到了一反例  (Counterexample) 是 341 ,341雖可整除 2340 - 1 ,但 341 = 11*31 是一合數。這一刻數學家才知道費馬小定理的逆命題是不成立的。事實上,在沒有計算機等電子工具之助的年代,要對費馬小定理的逆命題作測試是一件極不容易之事。除了 341 以外,人們還找到了 561 、 645 、 1105 、 1387 、 1729 、 1905 等 (OEIS A001567) 。他們全是合數也符合費馬小定理的要求,我們稱這些合數為費馬偽素數 (Fermat Pseudoprime) ,簡稱偽素數 (Pseudoprime) 。

 

以 a 為底的偽素數

若 n 為合數,且能整除 an-1-1,我們稱 n 為以 a 為底的偽素數 (Pseudoprime to Base a, 或 psp(a) ),這是把以往的偽素數觀念作了推廣。當然最先為數學家研究的會是以 2 為底的偽素數 (Pseudoprime to Base 2, 或 psp(2),如此類推,下同) ,這亦被稱作賽路斯數 (Sarrus Number) 或包列迪數 (Poulet Number) ,因為包列迪 (P. Poulet) 對這個問題花了不少精力。特別地,他在 1926年 計算了五千萬以內的偽素數,又於 1938年 計算到 108。我們已得知以某數為底的偽素數是有無限個之多。這無疑是對素數判定澆了一盤冷水。

 

下表列出一些以 2 或以 3 為底的偽素數:

底數 n
偽素數
斯洛恩數列
2
341、561、645、1105、1387、1729、1905、2047、2465、2701、2821、3277、4033、4369、4371、4681、...
3
91、121、286、671、703、949、1105、1541、1729、1891、2465、2665、2701、2821、3281、3367、3751、4961、...
2 & 3
1105、1729、2465、2701、2821、...

小小題外話,別以為以 2 為底的偽素數全是奇數,其實也有偶數,如 161038 或 215326 等 (OEIS A006935)。

 

有些數學家提出了一些構造 以 a 為底的偽素數的方法。

其中,1904年,薛波拉 (M. Cipolla) 給出了以下的方法:

設 a 不小於 2 , p 為奇素數且不能整除 a(a2 - 1) 。

令 n1= (ap- 1) / (a - 1) 及 n2= (ap+ 1) / (a + 1) ,n = n1* n2

則 n1 和 n2 均為奇數,而 n 是合成數亦同為 以 a 為底的偽素數了。

其後還有很多數學家提出不同的方法,本文不作冗述了。

 

下表為對於一些底的最小偽素數。
最小偽素數
2
341 = 11 * 31
3
91 = 7 * 13
5
217 = 7 * 31
7
25 = 5 * 5
2, 3
1105 = 5 * 13 * 17
2, 5
561 = 3 * 11 *17
2, 7
561 = 3 * 11 *17
3, 5
1541 = 23 * 67
3, 7
703 = 19 * 73
5, 7
561 = 3 * 11 * 17
2, 3, 5
1729 = 7 * 13 * 19
2, 3, 7
1105 = 5 * 13 * 17
2, 5, 7
561 = 3 * 11 * 17
3, 5, 7
29341 = 13 * 37 * 61
2, 3, 5, 7
29341 = 13 * 37 * 61

 

卡邁克爾數

在尋找偽素數的同時,數學家也對偽素數的個數進行了分析:

在 首 10億個自然數中,有 50847534 個素數,而以 2 為底的偽素數則只有 5597個。因此在整除 2n-1-1 的情況下,出現合數的機會僅有 5597/(5597+50847534) = 0.00011 ,即約 萬分之一。

而我們同時考慮以 2 和 3 為底的偽素數,則只有 1272 個。因此同時以整除 2n-1-1 和整除 3n-1-1 的情況下,碰上合數的機會便更低了,僅有 1272/(1272+50847534) = 0.000025。

於是以費馬小定理作素數判定仍有一定大的機會可信 , 符合費馬小定理逆命題的數 , 我們稱為擬素數 (Probable Prime) 。這擬素數一是素數,二是偽素數。人們自然會想,若我們把這測試擴張至其他式底,自然會把找到偽素數的機會降低,會降至 0 嗎?

 

答案是令人失望的不會。在 1912年美國數學家卡邁克爾 (Robert Daniel Carmichael 1879-1967) 發現數 561 能整除所有 a560-1 ,而 a 與 561 互素,但 561 = 3*11*17 是一合數。我們稱這樣的數為卡邁克爾數 (Carmichael Number)。卡邁克爾不單發現了這數的存在,還找到了一判定法則,這我們稱為卡邁克爾條件 (Carmichael Condition):

n 不能被一完全平方數整除。

n 是奇數,且至少含有三個不同的素因子。

對於 n 的每一個素因子 p ,n-1 能被 p-1 整除。

若 n 符合上述三條件,則 n 是卡邁克爾數,反之,若 n 是卡邁克爾數,n 亦會符合該三條件。

以我們先前談及的 561看看,這顯然滿足了首兩個條件。另一方面 561 = 3*11*17,而 561-1 = 560 = 24*5*7 ,3-1=2 、 11-1 = 10 = 2*5、17-1 = 16 = 24全是 560 的因子。

又用 8911 為例:

8911 = 7*19*67,顯然滿足了首兩個條件。

8911-1 = 8910 = 2*32*5*11

7-1 = 6 = 2*3、19-1 = 18 = 2*32、67-1 = 66 = 2*3*11 全是 8910 的因子。

故 8911 是卡邁克爾數。

 

在十萬以內,我們有 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973 和 75361 這十六個卡邁克爾數 (OEIS A002997)。若卡邁克爾數是有限的,我們可以定一上界 (Upper Bound) M ,在 M 以上的數,費馬小定理的逆定理便告成立,我們判斷素數也許會易得多。可惜答案是否定的,首先提出否定的是匈牙利數學家愛爾特希 (Paul Erdos 1913 - 1996)。接著,美國數學家奧爾福德 (William Robert 'Red' Alford 1937 - 2003)、 波門倫斯 (Carl Pomerance 1944 - ) 及英國數學家格蘭維爾 (Andrew Granville) 一同於 1994 年得證卡邁克爾數有無限個。但在給定素因子個數下,卡邁克爾數個數是否無限,則尚是未解之謎。

 

1939年,卓域克 (J. Chernick) 給出了一個建構卡邁克爾數的方法:

M3(m) = (6m + 1) (12m + 1) (18m + 1) ,若式中三個因子皆為素數,這 M3(m) 便是卡邁克爾數了。

同理,我們可以給出多於三個素因子的建構式:

M4(m) = (6m + 1) (12m + 1) (18m + 1) (36m + 1)

M5(m) = (6m + 1) (12m + 1) (18m + 1) (36m + 1) (72m + 1)

如此類推。運用這些數式,數學家不難找到更大或更多素因子的卡邁克爾數。

 

下表列出不同因子數目的最小卡邁克爾數:

 
因子數目 最小卡邁克爾數 展開式
3 561 3 * 11 * 17
4 41041 7 * 11 * 13 * 41
5 825265 5 * 7 * 17 * 19 * 73
6 321197185 5 * 19 * 23 * 29 * 37 * 137
7 5394826801 7 * 13 * 17 * 23 * 31 * 67 * 73
8 232250619601 7 * 11 * 13 * 17 * 31 * 37 * 73 * 163
9 9746347772161 7 * 11 * 13 * 17 * 19 * 31 * 37 * 41 * 641

(OEIS A006931)

 

其他的偽素數

後其數學家漸漸把符合一些素數性質的逆命題的合數稱為偽素數,我們便出現了很多不同的偽素數。如歐拉 - 雅可比偽素數 (Euler - Jacobi Pseudoprime) 或簡稱歐拉偽素數 (Euler Pseudoprime) 簡記 ejpsp(a)。另一個我們很常見到的是強偽素數 (Strong Pseudoprime),簡記 spsp(a)。留意,若我們單稱偽素數,通常是指費馬偽素數;別的偽素數,我們使用時會稱呼全名。關於歐拉 - 雅可比偽素數和強偽素數,詳可參閱《偽素數大家庭》一文。

 

參考文獻及網址

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, p. 61, 1987.

Beiler, A. H. Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, 1966.

Carmichael, R. D. "Note on a New Number Theory Function." Bull. Amer. Math. Soc. 16, 232-238, 1910.

Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 141-142, 1996.

Guy, R. K. "Carmichael Numbers." §A13 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 30-32, 1994.

Guy, R. K. "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes." §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.

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

Weisstein, E. W. "Carmichael Number." From MathWorld. http://mathworld.wolfram.com/CarmichaelNumber.html.

Weisstein, E. W. "Fermat's Little Theorem." From MathWorld. http://mathworld.wolfram.com/FermatsLittleTheorem.html.

Weisstein, E. W. "Pseudoprime." From MathWorld. http://mathworld.wolfram.com/Pseudoprime.html.