2.2　梅森尼数与费马数

本节介绍两类构造形式特殊的素数——梅森尼数与费马数，这两类数的特型2ⁿ±1引人注目。

1. 梅森尼数

定义：整数M_n＝2ⁿ-1称为第n个梅森尼（Mersenne）数。

判别梅森尼数是否为素数，首先有以下命题。

【命题1】　若M_n＝2ⁿ-1（n＞1）为素数，则指数n为素数。

【证明】　假设n不是素数，令n＝kd（1＜k，1＜d），2^d-1＞1，显然2^d-1能整除2ⁿ-1，即2ⁿ-1非素数。

由以上命题，要寻找梅森尼数为素数，只需在素数中寻找指数n。

例如，M₂＝2²-1＝3，M₃＝2³-1＝7都是素数。

注意：以上命题的逆命题并不成立，即若n为素数，M_n＝2ⁿ-1不一定是素数。例如，n＝11时，M₁₁＝2¹¹-1＝2047＝23×89，M₁₁不是素数。

1722年，双目失明的瑞士数学大师欧拉证明了2³¹-1＝2 147 483 647是一个素数，堪称当时世界上“已知最大素数”的纪录。

【编程探求】　试求出指数n＜50的所有梅森尼数。

（1）设计要点。

设置指数n循环（2~50），循环体中通过累乘t＝t∗2，得t＝2ⁿ。

根据梅森尼数的构造形式，对m＝t-1应用试商判别法实施素数判别。若m为素数，即为所寻求的梅森尼数，进行打印输出。

（2）求梅森尼数程序设计。

顺便指出，若2ⁿ-1为梅森尼素数，则n必为素数。以上程序的运行结果也可以验证这一点。若需求更大的梅森尼素数，指数n可限定为素数，以减少搜索量。

第25个梅森尼素数M_{21 701}和第26个梅森尼素数M_{23 209}是两名中学生于20世纪70年代发现的。

对于很大的素数n，要判断2ⁿ-1是否为素数，工作量很大，以上的枚举难以胜任，需要一些特殊的理论和方法。

1996年美国数学家及程序设计师乔治·沃特曼编制了一个梅森素数寻找程序，并把它放在网页上供数学家和数学爱好者免费使用，这就是著名的“因特网梅森尼素数大搜索”（GIMPS）项目。该项目采取网格计算方式，利用大量普通计算机的闲置时间来获得相当于超级计算机的运算能力。全球数万名志愿者参加该项目，并动用20多万台计算机联网进行大规模的分布式计算，以寻找新的梅森尼素数。

2006年12月4日，美国中密苏里大学Curtis Cooper和Steven Boone领导的工作组打破了他们自己的纪录，发现了最新的第44个梅森尼素数2^{23 582 657}-1，它是一个9 808 358位数。当前，梅森尼素数的纪录还在不断刷新。

2. 费马数

由梅森尼数M_n＝2ⁿ-1的形式可联想，形如2^m＋1的整数是否存在有规律性的素数？

【命题2】　若2^m＋1为素数，则m＝2ⁿ。

【证明】　若指数m有一个大于1的奇数因子k，令m＝kd，则

2^kd＋1＝（2^d）^k＋1＝（2^d＋1）（2^d（k-1）-…＋1）

而1＜2^d＋1＜2^kd＋1，故2^m＋1非素数。

由以上命题，定义整数F_n＝2²ⁿ＋1称为费马数。前5个费马数如下所示。

当n＝0时，2²⁰＋1＝3是素数；

当n＝1时，2²¹＋1＝5是素数；

当n＝2时，2²²＋1＝17是素数；

当n＝3时，2²³＋1＝257是素数；

当n＝4时，2²⁴＋1＝65 537是素数。

据此，费马于300多年前提出一个猜测：形如2²ⁿ＋1的整数是素数。

直到费马逝世后，欧拉于1732年才推翻了费马的猜测，指出：当n＝5时，2²⁵＋1＝4 294 967 297＝641×6 700 417，不是素数。后来又发现当n＝6，7，…时，2²ⁿ＋1都不是素数。

20世纪90年代数百名研究人员利用联网的1000多台计算机运行6个星期，将155位的F₉分解为7位、49位与99位的3个素数之积。此项成果曾被列为当时的十大科技成果之一。

当n≥5时，目前尚未发现形如2²ⁿ＋1的费马素数。

因此，有人推测，仅存在有限个费马素数。