梅森素数

梅森数和梅森素数的性质

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

• q ≡ 3 mod 4为素数。则 2q+1是素数 的充分必要条件是 2q+1整除M_q ，因此对于这些素数q（除了3），M_q不可能会是素数，前几个这样的素数q为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）：M_q = 6+x²。当q为3、5和7时，M_q为梅森素数，方程有整数解；q为合数4和15时，方程亦有整数解；q为其它自然数时，方程没有整数解。

• 如果p是奇素数，那么任何能整除2^p − 1的素数q都一定是1加上一个2p的倍数。例如，2¹¹ − 1 = 23×89，而23 = 1 + 2×11，89 = 1 + 8×11。

• 如果p是奇素数，那么任何能整除${\displaystyle 2^{p}-1}$ 的素数q都一定与${\displaystyle \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
  • 欧拉的一个关于形如1+6k的数的理论表明：M_q是素数当且仅当存在数对（x,y）使得M_q = (2x)² + 3(3y)²，其中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世纪，欧几里得（Euclid）证明如果M是梅森素数，那么${\displaystyle {\frac {M(M+1)}{2}}}$ 是完全数。
  • 18世纪，欧拉（Euler）证明所有的偶完全数都有这种形式。

• 是否有无穷多个梅森素数。
• 梅森素数如何分布。

• 头四个梅森素数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个梅森素数，而被人们誉为“素数大王”。

• 到2018年12月，我们知道了51个梅森素数；现在已知最大的素数是梅森素数M_82589933。像前几个一样，都是由因特网梅森素数大搜索（GIMPS）分布式计算项目发现的。
• 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_77232917，共有23249425位数^[3]。
• 2018年12月7日GIMPS项目M_82589933，共有24862048 位数^[1]。

梅森素数列表

  梅森遗漏的梅森素数

  GIMPS发现的梅森素数

  古代知道的梅森素数

  以试除法发现的梅森素数

  拉斐尔·米切尔·罗宾逊发现的梅森素数

  亚历山大·赫维兹发现的梅森素数

  Donald B. Gillies发现的梅森素数

  Walt Colquitt & Luke Welsh发现的梅森素数

下面表中列出了所有已知的梅森素数：  A000668

注：现在还不知道在第48个梅森素数（M_57885161）和第51个（M_82589933）之间是否还存在未知梅森素数，所以在其序号之前用^*标出，如果存在，会通知递补。

• （英文）Great Internet Mersenne Prime Search （页面存档备份，存于互联网档案馆） GIMPS计划
• （英文）Mersenne Primes: History, Theorems and Lists （页面存档备份，存于互联网档案馆） 梅森素数：历史，定理，以及梅森素数列表