梅森素数

古希腊数学家欧几里德就已证明素数有无穷多个，并提出一些素数可写成 “2P-1”（其中指数 P 也是素数）的形式，其中 17 世纪法国数学家、法兰西科学院奠基人马林·梅森（Martin Mersenne）是其中成果较为卓著的一位，因此数学界将 “2P-1” 型的素数称为 “梅森素数”。

1772 年，欧拉在双目失明的情况下，靠心算证明了 231-1（即 2147483647）是第 8 个梅森素数，这个记录一百多年内都没有人打破。下面是欧拉证明素数有无穷多个的过程，但是梅森素数是否有无穷多个还没有人能证明。

假使素数 p1，p2，p3……pn 只有那么多个，现在有新数 p=p1*p2*p3*……pn + 1，可见 p 无法被 p1，p2，p3……pn 任意一个整除，所以 p 是素数，那就和素数只有 n 个矛盾了，所以素数有无穷多个。

1996 年，乔治·沃特曼编制了一个梅森素数计算程序，后来发展成为 GIMPS（Great Internet Mersenne Prime Search，你可以从上面找到最新的第 48 个梅森素数发现的信息）项目，在超级计算机尝试之后，希望借助互联网和分布式计算的力量，寻找更大的梅森素数（现在已经有超过 180 个国家的近一百万台计算机参与计算）。

在寻找梅森素数的过程中，并不是漫无目的的。很容易证明，如果 2P-1 是素数，则 P 也一定是素数（这样我们就首先可以列出一个 “可疑梅森素数清单”，进一步的计算原理可以在这里找到），证明如下：

假设 2P-1 是素数的情况下，p 却是合数，那么令 p=r*s，r 和 s 都是大于 1 的正整数，那么 xrs-1 就可以拆解成 xs-1 乘以 xs(r-1) + xs(r-2) + … + xs + 1。所以，如果 p 是合数的话，2p-1 也会是合数（因为它可以拆出 2s-1 的因子来），这与假设命题不符，所以 p 就只能是素数了。 值得注意的是，对于 n>1，因为 x-1 可以整除 xn-1 ，所以如果要 xn-1 为素数的话，x-1 就必须等于 1 了，所以 x 就只能是 2 了。那么，就可以得到如下推论： 如果 a 和 n 都是大于 1 的正整数，如果 an-1 是素数的话，那么 a 就只能是 2，而且 n 必须为素数。

美国中央密苏里大学数学教授 Curtis Cooper 领导的研究小组于一周前的 1 月 25 日发现了已知的最大梅森素数——257885161−1（即 2 的 57885161 次方减 1）；该素数有 17425170 位，如果用普通字号将它连续打印下来，它的长度可超过 65 公里。

梅森素数的分布极不规则，连找到梅森素数的时间分布都极不规则，有时许多年未能找到一个，而有时则一下找到好几个，探索梅森素数的分布规律似乎比寻找新的梅森素数更为困难。中国的业余数学家周海中在 1992 年给出了梅森素数分布的精确表达式（“周氏猜测”）：

对于素数 p 和梅森素数 Mp=2P-1 ，当 22^n<p<22^(n+1) 时，Mp 有 2n+1-1 个；undefined 推论：当 p<22^(n+1) 时，Mp 有 2n+2－n－2 个。

梅森素数是测试计算机速度的一个有力工具，实际上寻找梅森素数的过程也推动了分布式计算的发展（数学这样的基础学科在寻找当前实际意义的时候往往如此，但是谁也无法预料对于未来的工程学科的发展能有多重大的意义），在实际领域，梅森素数也可以用来加密数据。由于把两个非常大的数相乘很容易，但是如果要把一个非常大的数分解，将是非常困难的，在这种加密设计中，要使用很大的素数，素数越大，理论上越不容易被破译。

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》

×Scan to share with WeChat