梅森素数

梅森素数是由梅森数而来。

所谓梅森数，是指形如2p－1的一类数，其中指数p是素数，常记为Mp 。如果梅森数是素数，就称为梅森素数。

用因式分解法可以证明，若2p－1是素数，则指数p也是素数；反之，当p是素数时，2p－1（即Mp）却未必是素数。前几个较小的梅森数大都是素数，然而梅森数越大，梅森素数也就越难出现。

目前仅发现50个梅森素数，最大的是 277232917－1（即2的77232917次方减1），有23249425位数。

是否存在无穷多个梅森素数是数论中未解决的著名难题之一。现今，可以证明：存在无穷多个梅森素数,见塔形素数

概述

素数是指在大于1的整数中只能被1和其自身整除的数。素数有无穷多个，但目前却只发现有极少量的素数能表示成 2p－1（p为素数）的形式，这就是梅森素数（如3、7、31、127等等）。它是以17世纪法国数学家马林·梅森的名字命名。

梅森素数是数论研究中的一项重要内容，自古希腊时代起人们就开始了对梅森素数的探索。由于这种素数具有着独特的性质（比方说和完全数密切相关）和无穷的魅力，千百年来一直吸引着众多数学家（包括欧几里得、费马、欧拉等）和无数的数学爱好者对它进行探究。

在现代，梅森素数在计算机科学、密码学等领域有重要的应用价值。它还是人类好奇心、求知欲和荣誉感的最好见证。

由来

早在公元前300多年，古希腊数学家欧几里得就开创了研究2p－1的先河。他在名著《几何原本》第九章中论述完全数时指出：如果2p－1是素数，则 2p－1（2p－1）是完全数。

1640年6月，费马在给马林·梅森（Marin Mersenne）的一封信中写道：“在艰深的数论研究中，我发现了三个非常重要的性质，我相信它们将成为今后解决素数问题的基础。” 这封信讨论了形如2p－1的数。

梅森在欧几里得、费马等人有关研究的基础上对2p－1作了大量的计算、验证，并于1644年在他的《物理数学随感》一书中断言：在不大于257的素数中，当p = 2、3、5、7、13、17、19、31、67、127、257 时，2p－1是素数，其它都是合数。前面的7个数（即2、3、5、7、13、17、19）已被前人所证实，而后面的4个数（即31、67、127、257）则是梅森自己的推断。由于梅森在科学界有着崇高的学术地位，人们对其断言都深信不疑。

后来人们才知道梅森的断言其实包含着若干错漏。不过他的工作却极大地激发了人们研究2p－1型素数的热情，使其摆脱作为 “完全数” 的附庸地位，可以说梅森的工作是2p－1型素数研究的一个转折点和里程碑。由于梅森学识渊博、才华横溢、为人热情以及最早系统而深入地研究2p－1型的数，为了纪念他，数学界就把这种数称为 “梅森数”，并以Mp记之（其中M为梅森姓名的首字母），即Mp=2p－1。如果梅森数为素数，则称之为 “梅森素数”（即2p－1型素数）。

寻找历程

2300多年来，人类仅发现50个梅森素数，由于这种素数珍奇而迷人，因此被人们誉为 “数海明珠” 。自梅森提出其断言后，人们发现的已知最大素数几乎都是梅森素数，因此寻找新的梅森素数的历程也就几乎等同于寻找新的最大素数的历程。

梅森素数的探寻难度极大，它不仅需要高深的理论和纯熟的技巧，而且需要进行艰苦的计算。

手算笔录时代

在计算能力低下的公元前，人们仅知道四个2p－1型素数：3、7、31和127，发现人已无从考证。1456年，又一个没有留下姓名的人在其手稿中给出了第5个2p－1型素数：8191。而在梅森之前，意大利数学家卡塔尔迪（1548～1626）也对这种类型的数进行了整理，他在1588年提出 131071 和 524287 也是素数，由此成为第一个在发现者榜单上留名的人。

手算笔录的时代，每前进一步，都显得格外艰难。1772年，在卡塔尔迪之后近200年，瑞士数学家欧拉（1707～1783）在双目失明的情况下，靠心算证明了 2147483647 是一个素数。这是人们找到的第8个梅森素数，它共有10位数，堪称当时世界上已知的最大素数。欧拉还证明了欧几里得关于完全数定理的逆定理：所有的偶完全数都具有 2p－1（2p－1）的形式，其中2p－1是素数。这表明梅森素数和偶完全数是一一对应的。

是素数，这是人们靠手工计算发现的最大梅森素数，长达39位。

，它们分别在1911年和1914年被数学家鲍尔斯（1875～1952）发现。

卢卡斯第一个否定了 “M67为素数” 这一自梅森断言以来一直被人们相信的结论，但他未能找到其因子。直到1903年，才由数学家科尔（1861～1926）算出267－1=193707721×761838257287。1922年，数学家克莱契克（1882～1957）进一步验证了M257并不是素数，而是合数。

在手工计算的漫长年代里，人们历尽艰辛，一共只找到12个梅森素数。

计算机时代

在1961年被赫维兹（1937～ ）证明是素数。

是素数。

通过大型计算机被找到。发现这一素数的美国伊利诺伊大学数学系全体师生感到无比骄傲，以至于把所有从系里发出的信件都敲上了 “211213－1是个素数” 的邮戳。

。

。

。但他未能确定M86243和M216091之间是否有异于M132049的梅森素数。

。

仍是他们的成果，史洛温斯基由于发现7个梅森素数，而被人们誉为 “素数大王” 。1996年发现的M1257787是迄今为止最后一个由超级计算机发现的梅森素数，数学家使用了Cray-T94，这也是人类发现的第34个梅森素数。

互联网时代

使用超级计算机寻找梅森素数实在太昂贵了，而且可以参与的人也有限，网格这一崭新技术的出现使梅森素数的搜寻又重新回到了 “人人参与” 的大众时代。20世纪90年代中后期，在美国程序设计师沃特曼和库尔沃斯基等人的共同努力下，建立了世界上第一个基于互联网的分布式计算项目——因特网梅森素数大搜索（GIMPS）。人们只要在GIMPS的主页上下载一个计算梅森素数的免费程序，就可以立即参加该项目来搜寻新的梅森素数。

，发现者来自法国、英国和美国。

。这是20世纪发现的最后一个梅森素数，也是人们知道的第一个超过100万位的素数。如果把它写下来的话，共有2098960位数字。

与史密斯发现的素数相比 “仅” 相差14万位数。

塔形素数

都是素数。

梅森素数表

M1～M12

2

3

1

古代

古人

3

7

1

5

31

2

7

127

3

13

8191

4

1456年

无名氏

17

131071

6

1588年

Pietro Cataldi

19

524287

6

1588年

Pietro Cataldi

31

2147483647

10

1772年

Leonhard Euler

61

2305843009213693951

19

1883年

Ivan Mikheevich Pervushin

89

618970019642690137449562111

27

1911年

Ralph Ernest Powers

107

162259276829213363391578010288127

33

1914年

Ralph Ernest Powers

127

170141183460469231731687303715884105727

39

1876年

Édouard Lucas

M13～M34

Raphael Mitchel Robinson

Raphael Mitchel Robinson

Raphael Mitchel Robinson

Raphael Mitchel Robinson

Raphael Mitchel Robinson

Landon Curt Noll & Laura Nickel

CDC Cyber 174

23,209

CDC Cyber 174

Walter Colquitt & Luke Welsh

132,049

David Slowinski & Paul Gage

David Slowinski & Paul Gage

David Slowinski & Paul Gage

M35～M50

3,021,377

GIMPS / Nayan Hajratwala

GIMPS / Michael Cameron

11,185,272

GIMPS / Hans-Michael Elvenich

GIMPS / Odd Magnar Strindmo

2008 / 08 / 23

注：　　1. 各表分别列出人工、借助计算机以及通过GIMPS项目发现的梅森素数。　　2. 目前还不确定在M47和M50之间是否还存在未知的梅森素数，其后的序号用 * 标出。　　3. 后两表梅森素数的数值从略。

分布规律

人们在寻找梅森素数的同时，对其重要性质——分布规律的研究也在进行着。从已发现的梅森素数来看，它们在正整数中的分布时疏时密、极不规则；从发现梅森素数的时间来看，有时许多年未能找到一个，而有时则一下找到好几个。梅森素数已发现的数量很少，且人们对其无穷性尚未可知，因此探索它的分布规律似乎比寻找新的梅森素数更为困难。数学家们在长期的摸索中，提出了一些猜想，英国数学家香克斯、美国数学家吉里斯、法国数学家托洛塔和德国数学家伯利哈特曾分别给出过关于梅森素数分布的猜测。但他们的猜测有一个共同点，就是都以近似表达式给出，而它们与实际情况的接近程度均未尽如人意。

周氏猜测的表达式虽然简单，但破解这一猜测的难度却很大。就目前研究文献来看，一些数学家和数学爱好者尝试破解周氏猜测，却至今未能证明或反证。

理论探索

梅森素数的计算公式

3*5/3.8*7/5.8*11/9.8*13/11.8*......*P/(P-1.2)-1=M

P是梅森数的指数，M是P以下的梅森素数的个数。

以下是计算的数值与实际数的情况：

指数5，计算2.947，实际3 ，误差0.053；

指数7，计算3.764，实际4 ，误差 0.236；

指数13，计算4.891，实际5，误差0.109；

指数17，计算5.339，实际6，误差0.661；

指数19，计算5.766，实际7，误差1.234；

指数31，计算6.746，实际8，误差1.254；

指数61，计算8.445，实际9，误差0.555；

指数89，计算9.201，实际10，误差0.799；

指数107，计算9.697，实际11，误差1.303；

指数127，计算10.036 ，实际12，误差1.964；

指数521，计算13.818，实际13，误差-0.818；

指数607，计算14.259，实际14，误差-0.259；

指数1279，计算16.306，实际15，误差-1.306；

指数2203，计算17.573，实际16，误差-1.573；

指数2281，计算17.941，实际17，误差-0.941；

这个公式是根据梅森素数的分布规律得出的。万数1为首，1被除外了，所以要减去1。在不考虑重叠问题，应该P减1就可以了，这里已考虑重叠问题，所以就P减1.2.在梅森数的指数渐渐增大，1.2是否合适，还要等实际检验。

所有的奇素数都是准梅森数（2^N-1）的因 子数，则梅森合数的因子数是只有素数中的一部份。

在2^N-1的数列中，一个素数作为素因子第一次出现在指数N的数中，这个素数作为因子数在2^N-1数列中就以N为周期出现。在这种数列中指数是偶数的都等于3乘以四倍金字塔数。

在2^N-1数列中，指数大于6的，除梅森素数外，都有新增一个或一个以上的素数为因子数，新增的因子数减1能被这个指数整除。

一个梅森合数的因子数只有唯一一次出现在一个梅森合数中。

一个是梅森素数的素数，它永远不是梅森合数的因子数。

一个是前面的梅森合数的因子数，它永远不会是后面的梅森合数的因子数。

所有梅森合数的数因子减1都能被这个梅森合数的指数整除，商是偶数。

一个素数在不是梅森合数的准梅森数中第一次以因子数出现，这个素数减1能被这个准梅森数的指数整除，商不一定是偶数。

梅森素数都在[4^(1-1)+4^(2-1)+4^(3-1)+......+4^(n-1)]*6+1数列中，括符里种数暂叫四倍金字塔数。

凡是一个素数是四倍金字塔数的因子数，以后就不是梅森合数的因子数。

在4^(1-1)+4^(2-1)+4^(3-1)+......+4^(n-1)数列中的数，有不等于6NM+-（N+M）的数乘以6加上1都是梅森素数。

在2^P-1平方根以下的素数都以素因子在以前准梅森数中出现了，那这个梅森数必是梅森素数。但它的逆定理是不成立的。如果还没有出现在以前的准梅森数中的素数，它也不定是梅森合数的因子数。

试证梅森素数

在指数n是无限多的2^n-1数列中梅森数和梅森素数只占其中的很少比例。

根据费马小定理，每一个奇素数都会以数因子出现在2^n-1数列中，只不过有些提前出现，有些最后出现。只有梅森素数和2^n+1形的素数才会最后出现，不是梅森素数和2^n+1形的素数才会提前出现。

每一个奇素数都十分有规律出现在2^n-1数列中，一个素数第一次出现在2^n-1数中（包括梅森素数），这个素数就以n为周期反复出现在2^n-1数列中，如3第一次出现在n=2中，指数能被2整除的都有3的因子数;7第一次出现在n=3，指数能被3整除的都有7的因子数;5第一次出现在n=4中,指数能被4整除都有5的因子数。一个素数出现在指数2^n-1数列中，不管n是素数不是素数，只要用素数去筛指数n都能包括2^n-1的数因子了。如果是合数前面的素数与它是重叠的所以不用重筛了。

这样就用所有的素数去筛无限多的自然数，剩下就是梅森素数了。

无限多的自然数任你筛多少次的几分之一，永远是无限多的。所以梅森素数是无限多的。

GIMPS项目

意义

梅森素数自古以来就是数论研究的一项重要内容，历史上有不少大数学家都专门研究过这种特殊形式的素数。自古希腊时代起直至17世纪，人们寻找梅森素数的意义似乎只是为了寻找完全数。但自梅森提出其著名断言后，特别是欧拉证明了欧几里得关于完全数定理的逆定理以来，偶完全数已仅仅是梅森素数的一种 “副产品” 了。

寻找梅森素数在当代已有了十分丰富的意义。寻找梅森素数是目前发现已知最大素数的最有效途径。自欧拉证明M31为当时最大的素数以来，在发现已知最大素数的世界性竞赛中，梅森素数几乎囊括了全部冠军。

寻找梅森素数是测试计算机运算速度及其他功能的有力手段，如M1257787就是1996年9月美国克雷公司在测试其最新超级计算机的运算速度时得到的。梅森素数在推动计算机功能改进方面发挥了独特作用。发现梅森素数不仅需要高功能的计算机，还需要素数判别和数值计算的理论与方法以及高超巧妙的程序设计技术等等，因此它的研究推动了 “数学皇后” ——数论的发展，促进了计算数学和程序设计技术的发展。

寻找梅森素数最新的意义是：它促进了分布式计算技术的发展。从最新的16个梅森素数是在因特网项目中发现这一事实，可以想象到网络的威力。分布式计算技术使得用大量个人计算机去做本来要用超级计算机才能完成的项目成为可能，这是一个前景非常广阔的领域。它的探究还推动了快速傅立叶变换的应用。

梅森素数在实用领域也有用武之地，现在人们已将大素数用于现代密码设计领域。其原理是：将一个很大的数分解成若干素数的乘积非常困难，但将几个素数相乘却相对容易得多。在这种密码设计中，需要使用较大的素数，素数越大，密码被破译的可能性就越小。

梅森素数这颗数学海洋中的璀璨明珠正以其独特的魅力，吸引着更多的有志者去寻找和研究。

大事记

公元前4世纪，古希腊数学家欧几里得在《几何原本》第九章中论述了完全数与2p－1型素数的关系，并提出有少量素数可表示成2p－1（p为素数）的形式，由此开创了研究2p－1型素数的先河。

15世纪，发现第5个2p－1型素数。

16世纪，意大利数学家卡塔尔迪开始对此类素数进行整理。

17世纪，法国数学家马林·梅森的工作成为2p－1型素数研究的转折点和里程碑之一，“梅森素数” 也由此得名。

18世纪，瑞士数学家欧拉证明了完全数定理的逆定理，并心算出第8个梅森素数M31，是当时已知的最大素数。

19世纪70年代，法国数学家卢卡斯提出了一个用来判别Mp是否为素数的重要定理——卢卡斯定理，并证明了M127是一个素数。卢卡斯的工作为梅森素数的研究提供了有力的工具。

19世纪末至20世纪初，数学家利用卢卡斯定理又陆续证明M61、M89、M107是素数。人类在 “手算笔录时代” 共发现12个梅森素数。

20世纪30年代，美国数学家莱默改进了卢卡斯的工作，给出了一个针对Mp的新的素性测试方法，即卢卡斯-莱默检验法。此方法在 “计算机时代” 发挥了重要作用，时至今日仍是检测梅森数素性的最佳方法。

电子计算机的发明革命化的改进了梅森素数的寻找，仅在1952年就找到5个梅森素数。此后为寻找梅森素数而使用的计算机功能也越来越强大。

1992年，中国学者周海中提出了一个关于梅森素数分布的猜想，并首次给出其分布的精确表达式。这一猜想在国际数学界引起较大反响，被命名为 “周氏猜测” 。

1996年，著名的 “因特网梅森素数大搜索”（GIMPS）项目建立，加快了寻找更大梅森素数的进程。

1999年3月，美国电子前沿基金会（EFF）向全世界宣布了为寻找更大的梅森素数而设立的奖金。至2008年8月，已发现超过1000万位的梅森素数。

2017年12月，发现第50个梅森素数。