梅森質數

梅森數是形如2ⁿ－1的數（n是正整數），記為${\textstyle M_{n}}$；如果梅森數是質數就稱梅森質數（英語：Mersenne prime）。

梅森預測表：n≤263

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的梅森質數，不過他錯誤包括了不是梅森質數的M₆₇和M₂₅₇，而遺漏了M₆₁、M₈₉和M₁₀₇。

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

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

相關命題和定理

梅森數和梅森質數的性質

• ${\displaystyle M_{n}=\sum _{i=0}^{n}{n \choose i}-1=\sum _{i=0}^{n-1}2^{i}}$。

• 如果${\textstyle p\equiv 3{\pmod {4}}}$為質數。則${\displaystyle 2p+1}$是質數的充分必要條件是${\displaystyle 2p+1\mid M_{p}}$ ，因此對於這些質數${\displaystyle p}$（除了3），${\displaystyle M_{p}}$不可能會是質數，前幾個這樣的質數${\displaystyle 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、… （OEIS數列A002515）

• 拉馬努金－南哥爾方程式（Ramanujan–Nagell Equation）：${\displaystyle M_{p}=6+x^{2}}$。當${\displaystyle p}$為3、5和7時，${\displaystyle M_{p}}$為梅森質數，方程式有整數解；${\displaystyle p}$為合數4和15時，方程式亦有整數解；${\displaystyle p}$為其它自然數時，方程式沒有整數解。

• 如果${\displaystyle p}$是奇質數，任何能整除${\displaystyle 2^{p}-1}$的質數${\displaystyle q}$都一定是${\displaystyle 2p}$的倍數加${\displaystyle 1}$，如2¹¹ − 1 = 23 × 89, 其中23 = 1 + (2 × 11) 且 89 = 1 + 4 × (2 × 11)。

• 如果${\displaystyle p}$是奇質數，任何能整除${\displaystyle 2^{p}-1}$的質數${\displaystyle q}$都一定與${\textstyle \pm 1{\pmod {8}}}$同餘。

梅森數和梅森質數的關係

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

• 由${\displaystyle 2^{ab}-1=(2^{a}-1)\times \sum _{i=0}^{b-1}2^{ia}}$知：「q是質數」是「M_q是質數」的必要條件，但不是充分條件。M₁₁＝2¹¹ − 1＝23×89是最小的反例。
• 對M_q（q是質數）有：
  • 若a是M_q的因數，則a有如下性質：
    • a ≡ 1 mod 2q
    • a ≡ ±1 mod 8
  • 形如6k＋1的數有歐拉理論表明：若且唯若有數對（x，y）使M_q＝（2x）²＋3（3y）²，M_q是質數，其中q≥5。
  • 最近，Bas jansen研究了等式M_q＝x²＋dy²（0≤d≤48），得出了d＝3時的新證明方法。
  • Reix發現q＞3時，M_q可寫成M_q＝（8x）²－（3qy）²＝（1＋Sq）²－（Dq）²；顯然，若有數對（x，y），M_q就是質數。

檢定梅森質數

• 盧卡斯－萊默檢定法是現在已知的檢測梅森數質數的最好的方法。
  • 該方法由愛德華·盧卡斯於1878年發現，並由德里克·亨利·萊默於1930年代改進，因此得名。
  • 該方法基於循環數列（英語：Derrick Henry Lehmer）的計算，其原理是：

M_n為質數若且唯若M_n整除S_n-2（S₀＝4，S_k＝S²_k−1 − 2，k＞0），此數列為4、14、194、37634、1416317954、2005956546822746114、4023861667741036022825635656102100994、…（OEIS數列A003010）

與完全數的關係

• 梅森質數與偶完全數有一一對應的關係，稱為歐幾里得－歐拉定理。
  • 前4世紀，歐幾里得證明如果M是梅森質數，則${\textstyle {\frac {M(M+1)}{2}}}$是完全數。
  • 18世紀，歐拉證明所有偶完全數都有這種形式。

相關問題和猜想

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

尋找梅森質數

• 頭四個梅森質數M₂、M₃、M₅、M₇在古代已知。
• 第五個梅森質數M₁₃在1461年之前發現；
• M₁₇和M₁₉兩數隨後在1588年由Cataldi發現。
• 17世紀法國數學家馬蘭·梅森列出了他認為的冪小於等於257的梅森質數，其中錯誤包括了不是質數的M₆₇和M₂₅₇，遺漏了M₆₁、M₈₉和M₁₀₇。這也是「梅森質數」一名的由來。
• 一個多世紀後的1750年，才由歐拉證實M₃₁是第8個梅森質數。
• 下個發現的梅森質數是由盧卡斯在1876年證明的M₁₂₇；
• 1883年，Pervushin證實M₆₁。
• M₈₉和M₁₀₇在20世紀早期由Powers分別在1911年和1914年發現。
• 發明電子計算機改革了梅森質數的尋找過程。第一項成功例子是證明M₅₂₁，它由萊默指導，用拉斐爾·米切爾·羅賓遜教授編寫的軟體，利用坐落在洛杉磯加利福尼亞大學的數據分析協會的，屬於美國國家標準局的西部自動計算機（SWAC）於1952年1月30日晚上10:00獲得，並且在隨後不到兩小時發現下個梅森質數M₆₀₇。在隨後的幾個月裡，使用同樣的程序發現了另外三個梅森質數M₁₂₇₉、M₂₂₀₃和M₂₂₈₁。
• 質數P值增大，搜尋梅森質數MP的過程都艱辛無比，但各國科學家及業餘研究者仍樂此不疲，激烈競爭；1979年2月23日，當美國克雷研究公司的計算機專家史洛溫斯基和納爾遜宣布找到第26個梅森質數M₂₃₂₀₉時才知諾爾在兩星期前已得到這結果。
• 為此，史洛溫斯基潛心發憤，花了一個半月用CRAY－1型計算機找到新梅森質數M₄₄₄₉₇，這紀錄成了當時不少美國報紙的頭版新聞。

• 他之後乘勝前進，使用改進了的CRAY－XMP型計算機在1983年至1985年間找到3個梅森質數M₈₆₂₄₃、M₁₃₂₀₄₉和M₂₁₆₀₉₁，但未能確定M₈₆₂₄₃和M₂₁₆₀₉₁之間是否有異於M₁₃₂₀₄₉的梅森質數。而到了1988年，科爾魁特和韋爾什使用NEC－FX2型超高速並行計算機果然捉到「漏網之魚」M₁₁₀₅₀₃。

• 沉寂4年後，1992年3月25日，英國原子能技術權威機構哈威爾實驗室有研究小組宣布找到梅森質數M₇₅₆₈₃₉。

• 1994年1月14日，史洛溫斯基和蓋奇為其公司再次奪回發現「已知最大質數」的桂冠——M₈₅₉₄₃₃；而下個梅森質數M_1257787仍是他們的成果，用CRAY－794超級計算機在1996年找到。

• 史洛溫斯基發現7個梅森質數，獲美譽「質數大王」。
• 2010年7月11日GIMPS確認M_20,996,011是第40個梅森質數。^[2]
• 2011年12月1日GIMPS確認M_24,036,583是第41個梅森質數。^[2]
• 2012年12月20日GIMPS確認M_25,964,951是第42個梅森質數。^[2]
• 2013年1月25日GIMPS發現M_57,885,161^[2]
• 2014年2月23日GIMPS確認M_30,402,457是第43個梅森質數。^[2]
• 2014年11月8日GIMPS確認M_32,582,657是第44個梅森質數。^[2]
• 2016年1月7日GIMPS發現M_74,207,281^[2]
• 2018年1月3日GIMPS發現的M_77,232,917有23249425位數^[3]。
• 2018年12月7日GIMPS的M_82,589,933有24862048位數^[4]。
• 2024年10月21日GIMPS的M_136,279,841有41024320位數^[1]。