梅森素數

法國數學家梅森 (Marin Mersenne 1588-1648)

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

 

由一封信說起

法國數學家梅森 (Marin Mersenne 1588-1648) 或譯作馬桑、梅桑,和業餘數學王子費馬 (Pierre de Fermat 1601-1665) 是好友。十七世紀,費馬也曾對完全數 (Perfect Number) 的問題有興趣,詳見本網另一文章《豐數、虧數和完全數》。他也必然考察過型如 2p-1 的數的素性 (Primality)。1640年 6月,費馬給梅森的信中提出三個定理,它們更是研究整數素性的基礎:

1. 若 n 不是素數,則 2n-1 也不是素數。

2. 若 n 是素數,則 2n-2 可被 2n 整除,即 2n-1=1 (mod n),即後來的「費馬小定理」(Fermat's Little Theorem)。

3. 若 n 是素數除了 2kn+1 這種型式的數以外, 2n-1 不能被其他型式的素數整除。

定理(1)相當於若 2n-1 是素數,則 n 是素數,反之則未必成立。

 

梅森數

梅森在其於1644年出版的著作《物理—數學探索》的序言中提出在不超過 257 的 55個素數中,僅當 p=2、3、5、7、13、17、19、31、67、127 和 257 ,這11個素數時, 2p-1 為素數。他本人驗證了前七個數,後四個數因計自算量太大而未能驗證。為了紀念他,後人把型如 2p-1 的數稱為梅森數 (Mersenne Number, Mp),型如 2p-1 的素數稱為梅森素數 (Mersenne Prime) ,上述斷言稱為梅森猜想 (Mersenne's Conjecture) 。然而這位梅森在其論作中竟有五個錯誤之多。

首先在1883年,俄國數學家佩爾武申 (Ivan Mikheevich Pervusin 1829-1900) 發現 M61 是素數,梅森算漏了一個。

接而在1903年,美國數學家科爾 (Frank Nelson Cole 1821-1926) 發現 M67 是合數,梅森算錯了一個,其實:

267-1=193707721*761838257287。

跟後波爾斯 (R. E. Powers) 在1911和1914年,又證明了 M89 和 M107 是素數。1922年克拉依切克 (Maurice Borisovich Kraitchik 1882-1957) 發現了 M257 是一合數。梅森合共漏掉了三個素數和誤把兩個合數看成素數。

 

反之,歐拉 (Leonhard Euler 1707-1783) 在1772年證明 M31 是素數,為梅森素數研究打了一枝強心針。

我們現在的計算法是法國數學家盧卡斯 (Edouard Lucas 1842-1891) 在1877年奠定的,他在1876年證明了 M127 是素數,其中

M127 = 1701 41183 46046 92317 31687 30371 58841 05727 ,這是沒有利用電子計算機找到最大的梅森素數。

其實在沒有電子計算機的年代後期,人們已有用機械計算機負責一些四則運算等工作,而非只用心算或筆算。但以此來作判斷大素數的工具,依然不易。而人們以機械計算機找尋到最大的素數是這個長 44 位的 (2148 + 1) / 17 = 2098 89366 57440 58648 61512 64256 61022 25938 63921。這素數我們稱為費勒素數 (Ferrer's Prime),但我們現在不用一秒便可判斷其素性,可見現代科技的先進。

 

更多的梅森數

1952年,美國人D.H.雷默 (Derrick Henry Lehmer 1905-1991) 和 魯賓遜 (Raphael M. Robinson 1911-1994) 證明了 p=521、p=607、p=1279、p=2203 和 p=2281 五個梅森素數。

1958年,瑞典數學家黎塞爾 (Hans Riesel 1929- ) 和 A.安德遜 (A. Anderson) 指出 p = 3217是梅森素數。

1962年,德國數學家赫爾維茨 (Adolf Hurwitz 1859-1919) 又發現 p = 4253 和 p = 4423 兩個梅森素數。

 

1964年,加拿大數學家吉里斯 (Donald Bruce Gillies 1928 - 1975) 為研究梅森素數作了一大躍進,他找到了 p=9689 、 p=9941 和 p=11213 三個梅森素數。吉里斯更指出小於 X 的梅森素數個數等於 2 ln ln X / ln 2 ,這吉里斯猜想 (Gilles Conjecture) 也和梅森素數其他相關理論一樣, 還是一個謎。

為記念梅森素數 p= 11213的發現而設計的郵印。

 

1971年,美國人塔克曼 (Bryant Tuckerman) 利用電子計算機的幫助,僅花了半小時,便發現了 p=19937 的梅森素數。和近300年前的梅森,花盡一生也計不了 p=257 ,可說是一大對比了。

1978年10月30日,十八歲的中學生尼克爾 (Laura A. Nickel) 和諾爾 (Landon Curt Noll, 1960 - ) 聯合發現了 p = 21701 的梅森素數。翌年二月,諾爾又單獨發現了 p = 23209 的梅森素數。電子計算機使尋找梅森素數的工作普及下去。

美國數學家斯諾文斯基 (David Slowinski) 在 1979 年至 1985 年六年內先後發現了四個梅森素數,分別是 p = 44497、 p = 86243 、p = 132049 和 p = 216091四個。在 1992 年至 1994 年間,他和蓋奇 (Paul Gage) 又找到第 32 至 34 個梅森素數,即 p = 756839、p = 859433 和 p = 1257787,合共找刑 7 個梅森素數之多,可謂一時無倆。

 

其後的梅森素數的發現都是借助 GIMPS (Great Internet Mersenne Prime Search 網上尋找梅森素數計劃) 的程式 (Program) 協助。但到底這 GIMPS 是什麼樣的組織?如何協助人找尋更大的梅森素數?更大的梅森素數又有多大?一連串的問題待解,且看另文《更大的梅森素數》和《梅森素數新方向》。欲想更了解梅森素數,可看附表《梅森素數表》。

 

雙梅森數

對梅森數或梅森素數的研究,現在還不過是起步階段而已。因其量太稀有和其數值太大,不利研究。我們對其性質,個數都未掌握。

會有無限個梅森素數嗎?現在誰也不知道。

有人曾提出一些與梅森素數的猜想:

當Mp是素數是,MMp (稱作雙梅森數 Double Mersenne Number) 也是一素數。這猜想對很小的梅森素數是正確的,但對 M13 = 8191 就不對了,因為有人證明 M8191 是合數 (Composite Number) ,該數長達 2466個位,這人正是羅賓遜 (Raphael M. Robinson 1911-1994)。1976年,德國數學家凱勒 (Wilfrid Keller 1937- ) 還找到 M8191 的其中一個因子 (Factor) 是 338193759479,詳見下表。

n
因子
發現者 (年份)
13
338193759479
凱勒 (Wilfrid Keller 1976)
17
231733529
羅賓遜 (Raphael M. Robinson 1957)
19
62914441
羅賓遜 (Raphael M. Robinson 1957)
31
29525752662031
夏和夫 (Guy Haworth 1983,1987)

而雙梅森素數 (Double Mersenne Prime) 有:7, 127, 2147483647, ..... (OEIS A077586)

 

卡塔蘭 - 梅森數

另一個猜想是由比利時數學家卡塔蘭 (Eugene Charles Catalan 1814-1894) 在 1876年左右提出的卡塔蘭猜想 (Catalan's Conjecture) ,他定義

C1 = 22-1 = 3 = M2 , C2 = 2C1-1 = 7 = M3 , C3 = 2C2-1 = 127 = M7

C4 = 2C3-1 = 2127-1 = M127 = 170141183460469231731687303715884105727

其中上述 Cn 稱為卡塔蘭 - 梅森數 (Catalan - Mersenne Number),若為素數,便是卡塔蘭 - 梅森素數 (Catalan - Mersenne Prime) 。我們知道除了開始的數個卡塔蘭 - 梅森數以外,其餘的也是雙梅森數。

 

卡塔蘭以為 Cn+1 = 2Cn-1 ,即所有卡塔蘭 - 梅森數, 都是素數。

這猜想是真是假,尚代驗證,懸疑未決。因為還未可判定 C5 的素性,但已知它不會有少於 1051 的素因子。

 

參考文獻及網址:

Bell, E. T. Mathematics: Queen and Servant of Science. Washington, DC: Math. Assoc. Amer., 1987.

Conway, J. H. and Guy, R. K. "Mersenne's Numbers." In The Book of Numbers. New York: Springer-Verlag, pp. 135-137, 1996.

Weisstein, E. W. "Catalan-Mersenne Number." From MathWorld. http://mathworld.wolfram.com/Catalan-MersenneNumber.html.

Weisstein, E. W. "Double Mersenne Number." From MathWorld. http://mathworld.wolfram.com/DoubleMersenneNumber.html.

Weisstein, E. W. "Mersenne Prime." From MathWorld. http://mathworld.wolfram.com/MersennePrime.html.

陳仁政 , 不可思議的 e , 北京 : 科學出版社 , p. 126-132 , 2005