梅森素数

梅森数是形如 $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 梅森素数：历史，定理，以及梅森素数列表