梅森素数

梅森数是形如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]。