梅森素数

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

1772年，欧拉在双目失明的情况下，靠心算证明了2³¹-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个国家的近一百万台计算机参与计算）。

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

假设2^P-1 是素数的情况下，p却是合数，那么令p=r*s，r和s都是大于1的正整数，那么 x^rs-1 就可以拆解成 x^s-1 乘以 x^s(r-1) + x^s(r-2) + … + x^s + 1。所以，如果p是合数的话，2^p-1 也会是合数（因为它可以拆出 2^s-1 的因子来），这与假设命题不符，所以p就只能是素数了。

值得注意的是，对于n>1，因为 x-1 可以整除 xⁿ-1 ，所以如果要 xⁿ-1 为素数的话，x-1 就必须等于1了，所以x就只能是2了。那么，就可以得到如下推论：

如果a和n都是大于1的正整数，如果 aⁿ-1 是素数的话，那么a就只能是2，而且n必须为素数。

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

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

对于素数p和梅森素数 Mp=2^P-1 ，当 2^{2^n}<p<2^{2^(n+1)} 时，Mp有 2ⁿ⁺¹-1 个；

推论：当 p<2^{2^(n+1)} 时，Mp有 2ⁿ⁺²－n－2 个。

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

文章系本人原创，转载请保持完整性并注明出自《四火的唠叨》