梅森素數
法國數學家梅森 (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