梅森素數

梅森數是形如2n-1的數(n是正整數),記為;如果梅森數是素數就稱梅森素數(英語:Mersenne prime)。

梅森數是根據17世紀法國數學家馬蘭·梅森的名字命名,他列出了n≤257的梅森素數,不過他錯誤包括了不是梅森素數的M67M257,而遺漏了M61M89M107

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是素數)有:
    • aMq的因數,則a有如下性質:
      • a ≡ 1 mod 2q
      • a ≡ ±1 mod 8
    • 形如6k+1的數有歐拉理論表明:當且僅當有數對(xy)使Mq=(2x2+3(3y2Mq是素數,其中q≥5。
    • 最近,Bas jansen研究了等式Mqx2dy2(0≤d≤48),得出了d=3時的新證明方法。
    • Reix發現q>3時,Mq可寫成Mq=(8x2-(3qy2=(1+Sq2-(Dq2;顯然,若有數對(xy),Mq就是素數。

檢驗梅森素數

Mn為素數當且僅當Mn整除Sn-2S0=4,SkS2k−1 − 2,k>0),此數列為4、14、194、37634、1416317954、2005956546822746114、4023861667741036022825635656102100994、…(OEIS數列A003010

與完全數的關係

相關問題和猜想

  • 梅森素數是否有無限個
  • 梅森素數如何分布

尋找梅森素數

  • 頭四個梅森素數M2M3M5M7在古代已知。
  • 第五個梅森素數M13在1461年之前發現;
  • M17M19兩數隨後在1588年由Cataldi發現。
  • 17世紀法國數學家馬蘭·梅森列出了他認為的冪小於等於257的梅森素數,其中錯誤包括了不是素數的M67M257,遺漏了M61M89M107。這也是「梅森素數」一名的由來。
  • 一個多世紀後的1750年,才由歐拉證實M31是第8個梅森素數。
  • 下個發現的梅森素數是由盧卡斯在1876年證明的M127
  • 1883年,Pervushin證實M61
  • M89M107在20世紀早期由Powers分別在1911年和1914年發現。
  • 發明電子計算機改革了梅森素數的尋找過程。第一項成功例子是證明M521,它由萊默指導,用拉斐爾·米切爾·羅賓遜教授編寫的軟件,利用坐落在洛杉磯加利福尼亞大學數據分析協會的,屬於美國國家標準局的西部自動計算機(SWAC)於1952年1月30日晚上10:00獲得,並且在隨後不到兩小時發現下個梅森素數M607。在隨後的幾個月裡,使用同樣的程序發現了另外三個梅森素數M1279M2203M2281
  • 素數P值增大,搜尋梅森素數MP的過程都艱辛無比,但各國科學家及業餘研究者仍樂此不疲,激烈競爭;1979年2月23日,當美國克雷研究公司計算機專家史洛溫斯基納爾遜宣布找到第26個梅森素數M23209時才知諾爾在兩星期前已得到這結果。
  • 為此,史洛溫斯基潛心發憤,花了一個半月用CRAY-1型計算機找到新梅森素數M44497,這紀錄成了當時不少美國報紙的頭版新聞。
  • 他之後乘勝前進,使用改進了的CRAY-XMP型計算機在1983年至1985年間找到3個梅森素數M86243M132049M216091,但未能確定M86243M216091之間是否有異於M132049的梅森素數。而到了1988年科爾魁特韋爾什使用NEC-FX2型超高速並行計算機果然捉到「漏網之魚」M110503
  • 到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 ColquittLuke 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)間是否還有未知梅森素數,其序號用*標出,如有會通知遞補。

  1. ^ 2009年4月12日首次有機器發現M4264萬3801,但直到6月4日才有人注意到,兩者皆可視為發現日期。
  2. ^ 2015年9月17日首次有機器發現M7420萬7281,但直到2016年1月7日才有人注意到,兩者皆可視為發現日期;GIMPS以後者為正式日期。

外部連結

參考

  1. ^ 1.0 1.1 Mersenne Prime Number discovery - 2^136279841-1 is Prime!. www.mersenne.org. [2024-10-21]. 
  2. ^ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 GIMPS Milestones. [2012-03-03]. (原始內容存檔於2016-09-03). 
  3. ^ GIMPS Project Discovers Largest Known Prime Number: 277,232,917-1. Mersenne Research, Inc. 2018年1月3日 [2018年1月14日]. (原始內容存檔於2018年1月3日). 
  4. ^ Mersenne Prime Discovery - 2^82589933-1 is Prime!. www.mersenne.org. [2018-12-24]. (原始內容存檔於2018-12-22).