梅森素數
此條目需要補充更多來源。 (2013年3月17日) |
梅森數是形如2n-1的數(n是正整數),記為;如果梅森數是素數就稱梅森素數(英語:Mersenne prime)。
P : Mn是梅森素數 — : Mn是梅森合數 青色:顯示正確 粉紅色:顯示錯誤 | ||||||||
n | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 |
Mn | P | P | P | P | — | P | P | P |
n | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 |
Mn | — | — | P | — | — | — | — | — |
n | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 |
Mn | — | P | — | — | — | — | — | P |
n | 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 |
Mn | — | — | — | P | — | — | P | — |
n | 137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |
Mn | — | — | — | — | — | — | — | — |
n | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 |
Mn | — | — | — | — | — | — | — | — |
n | 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 |
Mn | — | — | — | — | — | — | — | — |
梅森數是根據17世紀法國數學家馬蘭·梅森的名字命名,他列出了n≤257的梅森素數,不過他錯誤包括了不是梅森素數的M67和M257,而遺漏了M61、M89和M107。
n為合數時,一定為合數(當a整除b時,一定整除,反之亦然)。但n為素數時,不一定皆為素數,如和是素數,但不是素數。
截至2024年10月已知52個梅森素數,最大的是2136279841-1[1]。從1997年至今,所有新的梅森素數都由互聯網梅森素數大搜索(GIMPS)分布式計算項目發現。
相關命題和定理
梅森數和梅森素數的性質
- 。
- 如果 為素數。則 是素數的充分必要條件是 ,因此對於這些素數 (除了3), 不可能會是質數,前幾個這樣的素數 為11、23、83、131、179、191、239、251、359、419、431、443、491、659、683、719、743、911、1019、1031、1103、1223、1439、1451、1499、… (OEIS數列A002515)
- 拉馬努金-南哥爾方程(Ramanujan–Nagell Equation): 。當 為3、5和7時, 為梅森素數,方程有整數解; 為合數4和15時,方程亦有整數解; 為其它自然數時,方程沒有整數解。
- 如果 是奇素數,任何能整除 的素數 都一定是 的倍數加 ,如211 − 1 = 23 × 89, 其中23 = 1 + (2 × 11) 且 89 = 1 + 4 × (2 × 11)。
- 如果 是奇素數,任何能整除 的素數 都一定與 同餘。
梅森數和梅森素數的關係
下面的命題關注什麼梅森數是梅森素數。
- 由 知:「q是素數」是「Mq是素數」的必要條件,但不是充分條件。M11=211 − 1=23×89是最小的反例。
- 對Mq(q是素數)有:
- 若a是Mq的因數,則a有如下性質:
- a ≡ 1 mod 2q
- a ≡ ±1 mod 8
- 形如6k+1的數有歐拉理論表明:當且僅當有數對(x,y)使Mq=(2x)2+3(3y)2,Mq是素數,其中q≥5。
- 最近,Bas jansen研究了等式Mq=x2+dy2(0≤d≤48),得出了d=3時的新證明方法。
- Reix發現q>3時,Mq可寫成Mq=(8x)2-(3qy)2=(1+Sq)2-(Dq)2;顯然,若有數對(x,y),Mq就是素數。
- 若a是Mq的因數,則a有如下性質:
檢驗梅森素數
- Mn為素數當且僅當Mn整除Sn-2(S0=4,Sk=S2k−1 − 2,k>0),此數列為4、14、194、37634、1416317954、2005956546822746114、4023861667741036022825635656102100994、…(OEIS數列A003010)
與完全數的關係
相關問題和猜想
- 梅森素數是否有無限個
- 梅森素數如何分布
尋找梅森素數
- 頭四個梅森素數M2、M3、M5、M7在古代已知。
- 第五個梅森素數M13在1461年之前發現;
- M17和M19兩數隨後在1588年由Cataldi發現。
- 17世紀法國數學家馬蘭·梅森列出了他認為的冪小於等於257的梅森素數,其中錯誤包括了不是素數的M67和M257,遺漏了M61、M89和M107。這也是「梅森素數」一名的由來。
- 一個多世紀後的1750年,才由歐拉證實M31是第8個梅森素數。
- 下個發現的梅森素數是由盧卡斯在1876年證明的M127;
- 1883年,Pervushin證實M61。
- M89和M107在20世紀早期由Powers分別在1911年和1914年發現。
- 發明電子計算機改革了梅森素數的尋找過程。第一項成功例子是證明M521,它由萊默指導,用拉斐爾·米切爾·羅賓遜教授編寫的軟件,利用坐落在洛杉磯加利福尼亞大學的數據分析協會的,屬於美國國家標準局的西部自動計算機(SWAC)於1952年1月30日晚上10:00獲得,並且在隨後不到兩小時發現下個梅森素數M607。在隨後的幾個月裡,使用同樣的程序發現了另外三個梅森素數M1279、M2203和M2281。
- 素數P值增大,搜尋梅森素數MP的過程都艱辛無比,但各國科學家及業餘研究者仍樂此不疲,激烈競爭;1979年2月23日,當美國克雷研究公司的計算機專家史洛溫斯基和納爾遜宣布找到第26個梅森素數M23209時才知諾爾在兩星期前已得到這結果。
- 為此,史洛溫斯基潛心發憤,花了一個半月用CRAY-1型計算機找到新梅森素數M44497,這紀錄成了當時不少美國報紙的頭版新聞。
- 他之後乘勝前進,使用改進了的CRAY-XMP型計算機在1983年至1985年間找到3個梅森素數M86243、M132049和M216091,但未能確定M86243和M216091之間是否有異於M132049的梅森素數。而到了1988年,科爾魁特和韋爾什使用NEC-FX2型超高速並行計算機果然捉到「漏網之魚」M110503。
- 1994年1月14日,史洛溫斯基和蓋奇為其公司再次奪回發現「已知最大質數」的桂冠——M859433;而下個梅森素數M1257787仍是他們的成果,用CRAY-794超級計算機在1996年找到。
- 史洛溫斯基發現7個梅森素數,獲美譽「素數大王」。
- 到2018年12月已知51個梅森素數;現在已知最大的素數是梅森素數M82589933,像前幾個一樣都是由因特網梅森素數大搜索(GIMPS)分布式計算項目發現。
- 2010年7月11日GIMPS確認M2099萬6011是第40個梅森素數。[2]
- 2011年12月1日GIMPS確認M2403萬6583是第41個梅森素數。[2]
- 2012年12月20日GIMPS確認M2596萬4951是第42個梅森素數。[2]
- 2013年1月25日GIMPS發現M5788萬5161[2]
- 2014年2月23日GIMPS確認M3040萬2457是第43個梅森素數。[2]
- 2014年11月8日GIMPS確認M3258萬2657是第44個梅森素數。[2]
- 2016年1月7日GIMPS發現M7420萬7281[2]
- 2018年1月3日GIMPS發現的M7723萬2917有23249425位數[3]。
- 2018年12月7日GIMPS的M8258萬9933有24862048位數[4]。
- 2024年10月21日GIMPS的M1億3627萬9841有41024320位數[1]。
梅森素數列表
古代知道的梅森素數
以試除法發現的梅森素數
梅森遺漏的梅森素數
GIMPS發現的梅森素數
拉斐爾·米切爾·羅賓遜發現的梅森質數
亞歷山大·赫維茲發現的梅森質數
Donald B. Gillies發現的梅森質數
Walt Colquitt和Luke Welsh發現的梅森質數
下表列出所有已知的梅森素數: A000668
序 | n | Mn | Mn的位數 | 發現日期 | 發現者 | 算法 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 1 | 公元前5世紀 | 古希臘數學家 | |
2 | 3 | 7 | 1 | 公元前5世紀 | 古希臘數學家 | |
3 | 5 | 31 | 2 | 公元前3世紀 | 古希臘數學家 | |
4 | 7 | 127 | 3 | 公元前3世紀 | 古希臘數學家 | |
5 | 13 | 8191 | 4 | 1456年 | 無名氏 | 試除法 |
6 | 17 | 131071 | 6 | 1588年 | 彼得羅·卡塔爾迪 | 試除法 |
7 | 19 | 524287 | 6 | 1588年 | 彼得羅·卡塔爾迪 | 試除法 |
8 | 31 | 2147483647 | 10 | 1772年 | 萊昂哈德·歐拉 | 優化的試除法 |
9 | 61 | 2305843009213693951 | 19 | 1883年 | 伊萬·波佛辛 | 盧卡斯數列 |
10 | 89 | 618970019642690137449562111 | 27 | 1911年 | 拉爾夫·歐內斯特·鮑爾斯 | 盧卡斯數列 |
11 | 107 | 162259276829213363391578010288127 | 33 | 1914年 | 拉爾夫·歐內斯特·鮑爾斯 | 盧卡斯數列 |
12 | 127 | 170141183460469231731687303715884105727 | 39 | 1876年 | 愛德華·盧卡斯 | 盧卡斯數列 |
13 | 521 | 686479766013…291115057151 | 157 | 1952年1月30日 | 拉斐爾·米切爾·羅賓遜 | 盧卡斯-萊默檢驗法 |
14 | 607 | 531137992816…219031728127 | 183 | 1952年1月30日 | 拉斐爾·米切爾·羅賓遜 | 盧卡斯-萊默檢驗法 |
15 | 1279 | 104079321946…703168729087 | 386 | 1952年6月25日 | 拉斐爾·米切爾·羅賓遜 | 盧卡斯-萊默檢驗法 |
16 | 2203 | 147597991521…686697771007 | 664 | 1952年10月7日 | 拉斐爾·米切爾·羅賓遜 | 盧卡斯-萊默檢驗法 |
17 | 2281 | 446087557183…418132836351 | 687 | 1952年10月9日 | 拉斐爾·米切爾·羅賓遜 | 盧卡斯-萊默檢驗法 |
18 | 3217 | 259117086013…362909315071 | 969 | 1957年9月8日 | Hans Riesel | 盧卡斯-萊默檢驗法 |
19 | 4253 | 190797007524…815350484991 | 1281 | 1961年11月3日 | 亞歷山大·赫維茲 | 盧卡斯-萊默檢驗法 |
20 | 4423 | 285542542228…902608580607 | 1332 | 1961年11月3日 | 亞歷山大·赫維茲 | 盧卡斯-萊默檢驗法 |
21 | 9689 | 478220278805…826225754111 | 2917 | 1963年5月11日 | Donald B. Gillies | 盧卡斯-萊默檢驗法 |
22 | 9941 | 346088282490…883789463551 | 2993 | 1963年5月16日 | Donald B. Gillies | 盧卡斯-萊默檢驗法 |
23 | 1萬1213 | 281411201369…087696392191 | 3376 | 1963年6月2日 | Donald B. Gillies | 盧卡斯-萊默檢驗法 |
24 | 1萬9937 | 431542479738…030968041471 | 6002 | 1971年3月4日 | 布萊恩特·塔克曼 | 盧卡斯-萊默檢驗法 |
25 | 2萬1701 | 448679166119…353511882751 | 6533 | 1978年10月30日 | Landon Curt Noll & Laura Nickel | 盧卡斯-萊默檢驗法 |
26 | 2萬3209 | 402874115778…523779264511 | 6987 | 1979年2月9日 | Landon Curt Noll | 盧卡斯-萊默檢驗法 |
27 | 4萬4497 | 854509824303…961011228671 | 1萬3395 | 1979年4月8日 | Harry Nelson & David Slowinski | 盧卡斯-萊默檢驗法 |
28 | 8萬6243 | 536927995502…209433438207 | 2萬5962 | 1982年9月25日 | David Slowinski | 盧卡斯-萊默檢驗法 |
29 | 11萬0503 | 521928313341…083465515007 | 3萬3265 | 1988年1月28日 | Walt Colquitt & Luke Welsh | 盧卡斯-萊默檢驗法 |
30 | 13萬2049 | 512740276269…455730061311 | 3萬9751 | 1983年9月20日 | David Slowinski | 盧卡斯-萊默檢驗法 |
31 | 21萬6091 | 746093103064…103815528447 | 6萬5050 | 1985年9月6日 | David Slowinski | 盧卡斯-萊默檢驗法 |
32 | 75萬6839 | 174135906820…328544677887 | 22萬7832 | 1992年2月19日 | David Slowinski & Paul Gage | 盧卡斯-萊默檢驗法 |
33 | 85萬9433 | 129498125604…243500142591 | 25萬8716 | 1994年1月10日 | David Slowinski & Paul Gage | 盧卡斯-萊默檢驗法 |
34 | 125萬7787 | 412245773621…976089366527 | 37萬8632 | 1996年9月3日 | David Slowinski & Paul Gage | 盧卡斯-萊默檢驗法 |
35 | 139萬8269 | 814717564412…868451315711 | 42萬0921 | 1996年11月13日 | GIMPS/Joel Armengaud | 盧卡斯-萊默檢驗法 |
36 | 297萬6221 | 623340076248…743729201151 | 89萬5932 | 1997年8月24日 | GIMPS/Gordon Spence | 盧卡斯-萊默檢驗法 |
37 | 302萬1377 | 127411683030…973024694271 | 90萬9526 | 1998年1月27日 | GIMPS/Roland Clarkson | 盧卡斯-萊默檢驗法 |
38 | 697萬2593 | 437075744127…142924193791 | 209萬8960 | 1999年6月1日 | GIMPS/Nayan Hajratwala | 盧卡斯-萊默檢驗法 |
39 | 1346萬6917 | 924947738006…470256259071 | 405萬3946 | 2001年11月14日 | GIMPS/Michael Cameron | 盧卡斯-萊默檢驗法 |
40 | 2099萬6011 | 125976895450…762855682047 | 632萬0430 | 2003年11月17日 | GIMPS/Michael Shafer | 盧卡斯-萊默檢驗法 |
41 | 2403萬6583 | 299410429404…882733969407 | 723萬5733 | 2004年5月15日 | GIMPS/Josh Findley | 盧卡斯-萊默檢驗法 |
42 | 2596萬4951 | 122164630061…280577077247 | 781萬6230 | 2005年2月18日 | GIMPS/Martin Nowak | 盧卡斯-萊默檢驗法 |
43 | 3040萬2457 | 315416475618…411652943871 | 915萬2052 | 2005年12月15日 | GIMPS/Curtis Cooper及Steven Boone | 盧卡斯-萊默檢驗法 |
44 | 3258萬2657 | 124575026015…154053967871 | 980萬8358 | 2006年9月4日 | GIMPS/Curtis Cooper及Steven Boone | 盧卡斯-萊默檢驗法 |
45 | 3715萬6667 | 202254406890…022308220927 | 1118萬5272 | 2008年9月6日 | GIMPS/Hans-Michael Elvenich | 盧卡斯-萊默檢驗法 |
46 | 4264萬3801 | 169873516452…765562314751 | 1283萬7064 | 2009年4月12日[註 1] | GIMPS/Odd M. Strindmo | 盧卡斯-萊默檢驗法 |
47 | 4311萬2609 | 316470269330…166697152511 | 1297萬8189 | 2008年8月23日 | GIMPS/Edson Smith | 盧卡斯-萊默檢驗法 |
48 | 5788萬5161 | 581887266232…071724285951 | 1742萬5170 | 2013年1月25日 | GIMPS/Curtis Cooper | 盧卡斯-萊默檢驗法 |
49* | 7420萬7281 | 300376418084…391086436351 | 2233萬8618 | 2015年9月17日[註 2] | GIMPS/Curtis Cooper | 盧卡斯-萊默檢驗法 |
50* | 7723萬2917 | 467333183359…069762179071 | 2324萬9425 | 2017年12月26日 | GIMPS/Jon Pace | 盧卡斯-萊默檢驗法 |
51* | 8258萬9933 | 148894445742…325217902591 | 2486萬2048 | 2018年12月7日 | GIMPS/Patrick Laroche | 盧卡斯-萊默檢驗法 |
52 | 1億3627萬9841 | 881694327503…219486871551 | 4102萬4320 | 2024年10月21日 | GIMPS/Luke Durant | 盧卡斯-萊默檢驗法 |
註:現在還不知道第48個梅森素數(M57885161)和第51個(M82589933)間是否還有未知梅森素數,其序號用*標出,如有會通知遞補。
外部連結
- (英文)Great Internet Mersenne Prime Search (頁面存檔備份,存於網際網路檔案館) GIMPS計劃
- (英文)Mersenne Primes: History, Theorems and Lists (頁面存檔備份,存於網際網路檔案館) 梅森素數:歷史,定理,以及梅森素數列表
參考
- ^ 1.0 1.1 Mersenne Prime Number discovery - 2^136279841-1 is Prime!. www.mersenne.org. [2024-10-21].
- ^ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 GIMPS Milestones. [2012-03-03]. (原始內容存檔於2016-09-03).
- ^ GIMPS Project Discovers Largest Known Prime Number: 277,232,917-1. Mersenne Research, Inc. 2018年1月3日 [2018年1月14日]. (原始內容存檔於2018年1月3日).
- ^ Mersenne Prime Discovery - 2^82589933-1 is Prime!. www.mersenne.org. [2018-12-24]. (原始內容存檔於2018-12-22).