梅森素數

法國數學家梅森 (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) 的問題有興趣，詳見本網另一文章《豐數、虧數和完全數》。他也必然考察過型如 2^p-1 的數的素性 (Primality)。1640年 6月，費馬給梅森的信中提出三個定理，它們更是研究整數素性的基礎：

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

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

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

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

梅森數

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

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

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

2⁶⁷-1=193707721*761838257287。

跟後波爾斯 (R. E. Powers) 在1911和1914年，又證明了 M₈₉ 和 M₁₀₇ 是素數。1922年克拉依切克 (Maurice Borisovich Kraitchik 1882-1957) 發現了 M₂₅₇ 是一合數。梅森合共漏掉了三個素數和誤把兩個合數看成素數。

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

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

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

其實在沒有電子計算機的年代後期，人們已有用機械計算機負責一些四則運算等工作，而非只用心算或筆算。但以此來作判斷大素數的工具，依然不易。而人們以機械計算機找尋到最大的素數是這個長 44 位的 (2¹⁴⁸ + 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 兩個梅森素數。

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 是什麼樣的組織？如何協助人找尋更大的梅森素數？更大的梅森素數又有多大？一連串的問題待解，且看另文《更大的梅森素數》和《梅森素數新方向》。欲想更了解梅森素數，可看附表《梅森素數表》。

雙梅森數

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

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

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

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

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

卡塔蘭 - 梅森數

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

C₁ = 2²-1 = 3 = M₂ ， C₂ = 2^C1-1 = 7 = M₃ ， C₃ = 2^C2-1 = 127 = M₇ ，

C₄ = 2^C3-1 = 2¹²⁷-1 = M₁₂₇ = 170141183460469231731687303715884105727

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

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

這猜想是真是假，尚代驗證，懸疑未決。因為還未可判定 C₅ 的素性，但已知它不會有少於 10⁵¹ 的素因子。

參考文獻及網址：

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