Level: 0!

寻找数字中的宝石——梅森素数

我们在小学课本里就学到了“质数”这个概念，虽然在课本中一笔带过，但质数是数学中非常吸引人却又充满风险和意外的一个话题。在我看来，质数是数学最基本的一个要素，甚至是全宇宙最基础的元素与沟通基础。我曾经设想，如果有一天外星人造访地球并与地球人对话，那么一开始人类应该怎么跟外星人沟通呢？

如果是我，我会拿一堆石子，摆成2个，3个，5个，7个，11个，13个…如果外星人的数学水平够高，不是特别笨的话，他们肯定能会心地数出17个石子将其组成接下来的一堆。当然外星人能发展出访问地球的科技水平，了解质数肯定是其必备的基础知识。我认为与外星人聊数学一定是最有用的沟通方式，而与外星人聊文史哲或者物理化学，开始时恐怕都是对牛弹琴，鸡同鸭讲。

既然说到质数，我们聊一个可能很多人已经十分熟悉的质数相关话题：梅森素数。也许有人会问，不是说质数吗，怎么又出来素数了，质数其实又称为素数，为了配合讲清楚梅森素数，我们把文章中的质数统称为素数。梅森素数就是那种2p-1形式的素数，我相信读者已经在很多数学科普书中看到过梅森素数了。我们从小到大看过的数学科普书里，只要是讲到素数，都会提到梅森素数，而且经常是第一章。还有比较有意思的一点是，在不同时期出版的书中，都会提一下当前已经发现的最大的梅森素数，我也不能免俗，在此给大家刷新一下梅森素数的“存盘”进度。

这几年基本上每一到三年就会有一个新的梅森素数被发现。目前的最新纪录是2018年12月被发现的第51个梅森素数：282589933-1，它的位数已经达到2400多万。

梅森素数是根据17世纪的法国数学家马林·梅森的名字来命名的。但这并不是因为梅森素数是他发现的，也不是因为他发现了很多梅森素数。这种类型的素数在古希腊时期人们就已经注意到它们的存在了，但梅森是系统研究这种类型素数的第一人，而且他认为自己找出了指数小于257的所有梅森素数。不过梅森错判了两个，遗漏了三个，但这些错误是在很多年之后才被人们纠正的。

梅森认为：当p=2，3，5，7，13，17，19，31，67，127，257时，2p-1是素数。但是当p=67和257时，2p-1并不是素数。他遗漏了当p=61，89和107时这些数是素数的情况。让我们看看他误判的两个数的分解：

267-1=193707721×761838257287

2257-1=535006138814359×1155685395246619182673033×374550598501810936581776630096313181393

看了以上分解，你大概也不会笑话他错判了。可惜梅森没有留下他如何鉴定梅森素数的方法，大概他自己也知道自己的方法不能做到百分之百准确。

而现代人寻找梅森素数的方法如你所猜测的一样，人们是用计算机来寻找这种形式的素数的。从1997年开始，所有新的梅森素数都是由一个分布式计算项目发现的，这个项目的名称缩写叫GIMPS，意为“互联网梅森素数搜索计划”。每个人都可以参与这个计划，因为该网站会提供一个程序供人们下载，你只要下载并运行这个程序，就意味着参与了这个计划，从而为寻找更大的梅森素数贡献自己的力量。第50个梅森素数就是由一名美国联邦快递雇员，使用一台教堂闲置的老旧计算机，持续运行这个项目软件十年后发现的。

梅森素数为什么这么难找？你大概已经听说过检验一个素数是一个“多项式时间”的问题，即所谓P问题。

而检验梅森素数则比检验一般素数更为简单，有一个“卢卡斯-莱默检验法”。这种方法先由法国数学家爱德华·卢卡斯于1878年发现，再由美国数学家德瑞克·莱默于20世纪30年代改进完成。其方法相当简单：

首先定义序列Si，序列第一项的下标为0，且：

S0=4

之后每一项：

Si=Si2-1-2

该序列的开始几项就是4，14，194，37634…

而如果2p-1是素数，当且仅当Sp-2整除2p-1，即：

Sp-2≡0(mod Mp)

这个方法看上去很简单，而且仅需要O(p)的时间复杂度，但要考察的梅森素数都已经上千万，计算量仍然非常大，因此平均需要等上一年到三年。而每一个新的梅森素数与前一个的间隔也越来越大，因此寻找下一个梅森素数所花的时间也会更长。

顺便提一句，如果说鉴定一个数是否是素数是很难的问题，那么对一个大的合数找出其素因子，要比素性检验难成千上万倍。数学家根据以上“卢卡斯-莱默”检测法，虽然发现了很多2n-1形式的合数，但并不说明人们知道它们的质因子是几。

我们为什么要孜孜不倦地去寻找梅森素数呢？那是因为梅森素数有一些非常有意思的特点，而这些特点使人感到它似乎隐含着某种艰深的奥秘。

首先我们可以问，为什么只找2p-1这种形式的素数，而不找3p-1或者4p-1之类形式的素数呢？因为有一个定理：

如果ab-1是一个素数，那么这个a必须是2。即3p-1，4p-1，5p-1等都不可能是素数。这个定理的证明是十分简单的，你可以自行尝试一下，应该能很快发现其证明方法。然后还有一个定理：

如果2p-1是素数，那么这个p必须是素数。简短的证明思路是这样的：考虑任何一个2ab-1形式的数，其中a和b都是不为1的正整数。可以验证，它肯定有一个因子2a-1和另一个因子2b-1，这样它不可能是素数。所以，如果2p-1是一个素数，那么这个p也必须是一个素数。

你可能会想，太好了，要寻找梅森素数，范围已经非常小了，只要找2的素数次幂减1这样的数，其他类型的整数都不用考察了。但就像很多有关素数的命题一样，它们像是大自然跟人类开的一个玩笑。虽然我们知道2的素数次幂减1可能是素数，但如果真正去验证的话，你会发现它们大多数都不是素数，只是偶尔会有。

这很像去寻找宝石矿，你有些线索，你知道某个地方可能会有宝石，而且你也排除了其他绝大部分不可能有宝石矿的位置，于是你不停地往下挖，挖了半天还是什么东西都没有。所以有数学家把梅森素数比喻成“数字中的宝石”，对数学家来说，找到一个新的梅森素数，真的像挖到一块宝石一样可遇而不可求。

我们说梅森素数像宝石，不仅是因为稀有，还因为梅森素数有一个非常引人注目的特点，就是它与“完美数”是有直接的联系的。“完美数”的定义是：

如果针对一个自然数，将它所有的真因子相加，包括1，加起来正好是其本身的话，那它就是完美数。比如说6的真因子有1，2，3，而1+2+3=6，所以6是完美数。完美数本身是一个很大的话题，但完美数与梅森素数有一个美妙的联系，即一个偶数，如果它是完美数，当且仅当它有这种形式：

2p-1(2p-1)

且其中的2p-1是一个梅森素数，这被称为“欧几里得-欧拉定理”。也就是说偶完美数与梅森素数是一一对应的，这是一个非常神奇的结果，每当人们找出一个新的梅森素数，就等于找出了一个新的完美数，所以你也明白了数学家们为什么会这么开心。顺带说一句，现在还没有人发现奇数的完美数。很多数学家认为可能没有奇完美数，因为已经验证过，在101500以内，人们没有找到奇完美数。但像数论中的很多命题一样，如果没有被证明的话，谁都不敢打包票。

另外，梅森素数不但宝贵，而且很有用。有一种1997年由日本的松本真和西村拓土发明的随机数生成算法就叫“梅森旋转算法”，该算法因利用了一对梅森素数而得名。

接下来看看与梅森素数相关的一些猜想。第一个：有没有无穷多个梅森素数？这个“简单”的命题到现在我们都无法证明。虽然看上去没有什么理由阻止宇宙间有无穷多个梅森素数，绝大多数数学家也都认为这个命题是真的，但就是证明不了。

第二个：有没有无穷多个梅森数是合数？你可能会说：这不是废话吗？我们不是已经验证过这么多，而且大部分2p-1的数都是合数吗？但是数学中出现过那种前期虽然有很多例证，但是最后出现反例，从而推翻猜想的情况。尽管大部分数学家确实认为有无穷多个梅森数是合数，但这个问题到现在的的确确还只是一个猜想！它与上面的猜想两者至少有一个为真命题，当然，也可能都是真命题。

欧拉曾证明：

如果k>1且p=4k+3是素数，则2p+1是素数，当且仅当：2p=1(mod 2p+1)

这意味着：如果有无穷多个p=4k+3和2p+1都是素数的话，就有无穷多个梅森素数是合数。

第三个：是不是每一个梅森数，它的因子当中都不含有完全平方数呢？该命题的意思是：

如果2p-1是素数的话，它的因子当中当然不会含有完全平方数。如果2p-1是合数，那么我们能对它进行质因数分解。在分解的结果中，是不是每个素因子只出现一次，即它不可能被任何完全平方数（1除外）整除。目前此猜想对所有是合数的梅森数都适用，以下是另两个梅森数的因子分解例子，其中每个因子都只出现一次：

211-1=23×89

271-1=228479×48544121×212885833

此猜想问的是这是否对所有梅森数都成立，目前仍未可知。而这个猜想跟另一个相当有趣的素数——“韦弗利素数”是相关的。“韦弗利素数”是这种数：

如果一个素数p，满足p2整除2p-1-1，则称其为“韦弗利素数”。

数学家在4.96×1017内仅发现了两个韦弗利素数：1093和3511，所以它比梅森素数更稀有！但是这两个素数的平方不是目前已知任何梅森数的因子，也不知道是否有无穷多个韦弗利素数，它简直比梅森素数更神秘。

第四个猜想更有意思。有人构造了这样一个数列，取数列第一项为：

a1=2；

第二项取前一项的值作为指数，计算：

a2=2-1=22-1=3；3是一个素数。

第三项取第二项的值作为指数，有：

a3=2 a2-1=23-1=7；7是一个素数。

如此推算，可得a4=127，a5也是素数。我们很自然地会猜想是不是所有如此推得的an都是素数呢？

看上去挺有道理的，但是基本所有数学家都认为这个猜想是错的，而且很可能a6就不是素数，唯一的障碍就是a6太大了！

a6会有多大呢？a5=2127-1就有三十多位数了，而我们验证过的最大梅森素数的指数才只有9位。所以要验证a6这个梅森数是否为素数，用现有方法是不可能做到的。

那么数学家为何能如此斩钉截铁地说它是假命题呢？历史经验告诉我们，对数论方面的命题，再多的数字例证都不足为据。更何况在与素数相关的命题中，无数的“反例”都是出现在天文数字之后，而这个命题只有5个例证，简直微不足道。

素数的各种表现告诉我们，想要找出一个素数的简单生成公式是不可能的。上千年以来，已有无数的人想构造一个简单的公式去产生素数序列，但或早或晚都失败了。寻找能够“有效”产生素数序列的公式，仍然是数学中非常困难的课题。

甚至有个数学家理查德·盖伊，他提出了一个颇具幽默感的“小数规律”，是相对于概率论的“大数规律”提出的。其意思是说：对一个数学猜想来说，提供再多的具体实证例子，于这个猜想本身是否成立，产生的影响都非常小。不管你提供了几万个甚至几亿个实例，其影响都可以忽略不计。不久前有人使用电脑程序去验证过a6，结果在1051内没有找到它的因子，导致他没有信心继续找下去了。但这丝毫不能动摇数学家认为a6是个合数的想法。

最后，还有人提出一个更夸张的猜想：如果梅森素数2p-1中的p本身是个梅森素数，是否产生数字的也都是梅森素数？即如果2p-1是素数，是否-1也是素数？这种素数被称为“双重梅森素数”（Double Mersenne Primes）。

当p=2，3，5，7时，该命题都成立。但有意思的是这个命题在p>7之后，都是反例了。所以现在的猜想是：在p=7之后有没有更大的双重梅森素数？双重梅森素数是否有无穷多个？有数学家猜想“双重梅森素数”只有我们已发现的这4个，但仍然是因为数字增长太快的原因，我们至今无法确切解答这个问题。

以上有关梅森素数的相关话题差不多讲完了，不知道你是否感受到这些“数字中的宝石”的珍贵。我的最大感想是：谈及与素数相关的命题时要非常小心，不能简单找到几个例子就轻下结论。

思考题

大老李陪你一起“玩”

1.马兰·梅森遗漏了当p=61，89和107时的梅森素数。请你用“卢卡斯-莱默检测法”检查一下它们是否确实为素数。

2.已知一个梅森素数，请你验证双重梅森数