梅森素數

梅森數是形如 $2^n -1$ 的數（其中$n$ 是正整數），記為$M_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\leq 257$ 的梅森素數，不過他錯誤的包括了不是梅森素數的$M_{67}$ 和 $M_{257}$，而遺漏了 $M_{61}$、$M_{89}$和 $M_{107}$。

$n$ 為合數時，$M_n$一定為合數（當 $a$ 整除 $b$ 時，$M_a$一定整除$M_b$，反之亦然）。但 $n$ 為素數時，$M_n$不一定皆為素數，如 $M_2=2^2-1=3$ 和 $M_3=2^3-1=7$ 是素數，但 $M_{11}=2^{11}-1=2047=23\times 89$ 不是素數。

截至2024年10月已知52個梅森素數，最大的是2136279841－1。從1997年至今，所有新的梅森素數都是由網際網路梅森素數大搜索（GIMPS）分布式計算項目發現的。

## 相關命題和定理

### 梅森數和梅森素數的性質

- $M_n = \sum_{i=0}^{n} {n \choose i} - 1 = \sum_{i=0}^{n-1} 2^i$。
- 如果$p \equiv 3 \pmod 4$為素數。則$2p+1$是素數的充分必要條件是$2p+1 \mid M_p$，因此對於這些素數$p$（除3之外），$M_p$不可能會是質數。前幾個這樣的素數$p$有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、...
- 拉馬努金-南哥爾方程（Ramanujan–Nagell Equation）：$M_p=6+x^2$。當$p$為3、5和7時，$M_p$為梅森素數，方程有整數解；當$p$為合數4和15時，方程亦有整數解；當$p$為其它自然數時，方程沒有整數解。
- 如果$p$是奇素數，任何能整除$2^p-1$的素數$q$都一定是$2p$的倍數加$1$，如211 − 1 = 23 × 89, 其中 且。
- 如果$p$是奇素數，任何能整除$2^p-1$的素數$q$都一定與$\pm 1 \pmod 8$同餘。

### 梅森數和梅森素數的關係

下面的命題關注什麼梅森數是梅森素數。

- 由$2^{ab}-1=(2^a-1)\times\sum_{i=0}^{b-1}2^{ia}$知：「$q$ 是素數」是「$M_q$ 是素數」的必要條件，但不是充分條件。$M_{11}=2^{11} - 1=23\times 89$ 是最小的反例。
- 若 $a$ 是 $M_q$ 的因數，則 $a$ 有如下性質：
- $$a \equiv 1 \bmod 2q$$
- $$a \equiv \pm 1 \bmod 8$$
- 形如 $6k+1$ 的數有歐拉理論表明：若且唯若有數對 $(x,y)$ 使$M_q=(2x)^2+3(3y)^2$，$M_q$ 是素數，其中 $q \geq 5$。
- 最近，Bas jansen研究了等式$M_q=x^2+dy^2\ (0\leq d\leq 48)$，得出了$d=3$時的新證明方法。
- Reix發現 $q>3$ 時，$M_q$ 可寫成 $M_q=(8x)^2-(3qy)^2=(1+Sq)^2-(Dq)^2$；顯然，若有數對$(x,y)$，則$M_q$ 是素數。

### 檢驗梅森素數

盧卡斯-萊默檢驗法是現在已知的檢測梅森數素數的最好的方法。

- 該方法由愛德華·盧卡斯於1878年發現，並由德里克·亨利·萊默於1930年代改進，因此得名。
- 該方法基於循環數列的計算，其原理是：

$M_n$ 為素數若且唯若 $M_n$ 整除 $S_{n-2}$（$S_0=4$，$S_k=S^2_{k-1}-2$，$k>0$），此數列為4、14、194、37634、1416317954、2005956546822746114、4023861667741036022825635656102100994、…

### 與完全數的關係

梅森素數與偶完全數有一一對應的關係，稱為歐幾里得-歐拉定理。

- 前4世紀，歐幾里得證明了，若M是梅森素數，則$\frac{M(M+1)}{2}$是完全數。
- 18世紀，歐拉證明了所有偶完全數都有這種形式。

## 相關問題和猜想

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

## 尋找梅森素數

- 頭四個梅森素數$M_2$、$M_3$、$M_5$、$M_7$在古代已知。
- 第五個梅森素數$M_{13}$在1461年之前發現。
- $M_{17}$和$M_{19}$兩數隨後在1588年由Cataldi發現。
- 17世紀法國數學家馬蘭·梅森列出了他認為的冪小於等於257的梅森素數，其中錯誤包括了不是素數的$M_{67}$和$M_{257}$，遺漏了$M_{61}$、$M_{89}$和$M_{107}$。這也是「梅森素數」一名的由來。
- 一個多世紀後的1750年，才由歐拉證實$M_{31}$是第8個梅森素數。
- 下個發現的梅森素數是由盧卡斯在1876年證明的$M_{127}$。
- 1883年，Pervushin證實$M_{61}$。
- $M_{89}$和$M_{107}$在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。
- 沉寂4年後，1992年3月25日，英國原子能技術權威機構哈威爾實驗室有研究小組宣布找到梅森素數M756839。
- 1994年1月14日，史洛溫斯基和蓋奇為其公司再次奪回發現「已知最大質數」的桂冠——M859433；而下個梅森素數M1257787仍是他們的成果，用CRAY－794超級計算機在1996年找到。
- 史洛溫斯基發現7個梅森素數，獲美譽「素數大王」。
- 2010年7月11日GIMPS確認M20,996,011是第40個梅森素數。
- 2011年12月1日GIMPS確認M24,036,583是第41個梅森素數。
- 2012年12月20日GIMPS確認M25,964,951是第42個梅森素數。
- 2013年1月25日GIMPS發現M57,885,161
- 2014年2月23日GIMPS確認M30,402,457是第43個梅森素數。
- 2014年11月8日GIMPS確認M32,582,657是第44個梅森素數。
- 2016年1月7日GIMPS發現M74,207,281
- 2018年1月3日GIMPS發現的M77,232,917有23249425位數。
- 2018年12月7日GIMPS的M82,589,933有24862048位數。
- 2024年10月21日GIMPS的M136,279,841有41024320位數。

### 梅森素數列表

下表列出所有已知的梅森素數：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｜2,203｜147597991521...686697771007｜664｜1952年10月7日｜拉斐爾·米切爾·羅賓遜｜盧卡斯－萊默檢驗法

17｜2,281｜446087557183...418132836351｜687｜1952年10月9日｜拉斐爾·米切爾·羅賓遜｜盧卡斯－萊默檢驗法

18｜3,217｜259117086013...362909315071｜969｜1957年9月8日｜Hans Riesel｜盧卡斯－萊默檢驗法

19｜4,253｜190797007524...815350484991｜1,281｜1961年11月3日｜亞歷山大·赫維茲｜盧卡斯－萊默檢驗法

20｜4,423｜285542542228...902608580607｜1,332｜1961年11月3日｜亞歷山大·赫維茲｜盧卡斯－萊默檢驗法

21｜9,689｜478220278805...826225754111｜2,917｜1963年5月11日｜Donald B. Gillies｜盧卡斯－萊默檢驗法

22｜9,941｜346088282490...883789463551｜2,993｜1963年5月16日｜Donald B. Gillies｜盧卡斯－萊默檢驗法

23｜11,213｜281411201369...087696392191｜3,376｜1963年6月2日｜Donald B. Gillies｜盧卡斯－萊默檢驗法

24｜19,937｜431542479738...030968041471｜6,002｜1971年3月4日｜布萊恩特·塔克曼｜盧卡斯－萊默檢驗法

25｜21,701｜448679166119...353511882751｜6,533｜1978年10月30日｜Landon Curt Noll & Laura Nickel｜盧卡斯－萊默檢驗法

26｜23,209｜402874115778...523779264511｜6,987｜1979年2月9日｜Landon Curt Noll｜盧卡斯－萊默檢驗法

27｜44,497｜854509824303...961011228671｜13,395｜1979年4月8日｜Harry Nelson & David Slowinski｜盧卡斯－萊默檢驗法

28｜86,243｜536927995502...209433438207｜25,962｜1982年9月25日｜David Slowinski｜盧卡斯－萊默檢驗法

29｜110,503｜521928313341...083465515007｜33,265｜1988年1月28日｜Walt Colquitt & Luke Welsh｜盧卡斯－萊默檢驗法

30｜132,049｜512740276269...455730061311｜39,751｜1983年9月20日｜David Slowinski｜盧卡斯－萊默檢驗法

31｜216,091｜746093103064...103815528447｜65,050｜1985年9月6日｜David Slowinski｜盧卡斯－萊默檢驗法

32｜756,839｜174135906820...328544677887｜227,832｜1992年2月19日｜David Slowinski & Paul Gage｜盧卡斯－萊默檢驗法

33｜859,433｜129498125604...243500142591｜258,716｜1994年1月10日｜David Slowinski & Paul Gage｜盧卡斯－萊默檢驗法

34｜1,257,787｜412245773621...976089366527｜378,632｜1996年9月3日｜David Slowinski & Paul Gage｜盧卡斯－萊默檢驗法

35｜1,398,269｜814717564412...868451315711｜420,921｜1996年11月13日｜GIMPS／Joel Armengaud｜盧卡斯－萊默檢驗法

36｜2,976,221｜623340076248...743729201151｜895,932｜1997年8月24日｜GIMPS／Gordon Spence｜盧卡斯－萊默檢驗法

37｜3,021,377｜127411683030...973024694271｜909,526｜1998年1月27日｜GIMPS／Roland Clarkson｜盧卡斯－萊默檢驗法

38｜6,972,593｜437075744127...142924193791｜2,098,960｜1999年6月1日｜GIMPS／Nayan Hajratwala｜盧卡斯－萊默檢驗法

39｜13,466,917｜924947738006...470256259071｜4,053,946｜2001年11月14日｜GIMPS／Michael Cameron｜盧卡斯－萊默檢驗法

40｜20,996,011｜125976895450...762855682047｜6,320,430｜2003年11月17日｜GIMPS／Michael Shafer｜盧卡斯－萊默檢驗法

41｜24,036,583｜299410429404...882733969407｜7,235,733｜2004年5月15日｜GIMPS／Josh Findley｜盧卡斯－萊默檢驗法

42｜25,964,951｜122164630061...280577077247｜7,816,230｜2005年2月18日｜GIMPS／Martin Nowak｜盧卡斯－萊默檢驗法

43｜30,402,457｜315416475618...411652943871｜9,152,052｜2005年12月15日｜GIMPS／Curtis Cooper及Steven Boone｜盧卡斯－萊默檢驗法

44｜32,582,657｜124575026015...154053967871｜9,808,358｜2006年9月4日｜GIMPS／Curtis Cooper及Steven Boone｜盧卡斯－萊默檢驗法

45｜37,156,667｜202254406890...022308220927｜11,185,272｜2008年9月6日｜GIMPS／Hans-Michael Elvenich｜盧卡斯－萊默檢驗法

46｜42,643,801｜169873516452...765562314751｜12,837,064｜2009年4月12日｜GIMPS／Odd M. Strindmo｜盧卡斯－萊默檢驗法

47｜43,112,609｜316470269330...166697152511｜12,978,189｜2008年8月23日｜GIMPS／Edson Smith｜盧卡斯－萊默檢驗法

48｜57,885,161｜581887266232...071724285951｜17,425,170｜2013年1月25日｜GIMPS／Curtis Cooper｜盧卡斯－萊默檢驗法

49｜74,207,281｜300376418084...391086436351｜22,338,618｜2015年9月17日｜GIMPS／Curtis Cooper｜盧卡斯-萊默檢驗法|盧卡斯－萊默檢驗法

50｜77,232,917｜467333183359...069762179071｜23,249,425｜2017年12月26日｜GIMPS／Jon Pace｜盧卡斯-萊默檢驗法|盧卡斯－萊默檢驗法

51、｜82,589,933｜148894445742...325217902591｜24,862,048｜2018年12月7日｜GIMPS／Patrick Laroche｜盧卡斯-萊默檢驗法|盧卡斯－萊默檢驗法

52、｜136,279,841｜881694327503...219486871551｜41,024,320｜2024年10月21日｜GIMPS／Luke Durant｜盧卡斯-萊默檢驗法|PRP(可能質數)測試

註：現在還不知道第50個梅森素數（M77,232,917）和第52個（M136,279,841）之間是否還有未知梅森素數，其序號用*標出，如有會通知遞補。

## 外部連結

- Great Internet Mersenne Prime Search GIMPS計劃
- Mersenne Primes: History, Theorems and Lists 梅森素數：歷史，定理，以及梅森素數列表