所谓梅森素数,是以17世纪法国修道士M.梅森的名字命名的.梅森在1644年出版的著作<<物理数学随感>>的序言中宣称,对于n=2,3,5,7,13,17,19,31,67,127,257,数Mn=2ⁿ-1是素数,而对于其他所有小于257的数n,Mn是合数.但是,这里出现了5个错误,M67,M257不是素数,而M61,M89,M107是素数.显然,要使Mn是素数,n本身必须是素数,但是反过来,n是素数,Mn却不一定是素数,例如虽然11是素数,可是M11=2047=23X89是合数.由费马小定理知道,若p为素数,而a不是p的倍数,则a^p-1-1恒是p的倍数.例如2⁶-1是7的倍数.但是也有可能存在比p-1更小的数b就能使得2^b-1是p的倍数了,例如2³-1就能够被7整除了.很容易证明p-1是b的倍数,即p=rb+1.表面上看来对于寻找Mp的因子费马小定理一点儿也帮不上忙,但是已经证明,对于底数2来说,指数p-1可除以2而不影响该数用p去除时的可除性,如p在除以8时余数为1或为7的话,换言之,即其形状为8r+1或8r+7.从而可以推出:

            　　 2^[(8r+1)-1]/2-1与2^[(8r+7)-1]/2-1

　　可以被p整除.在前一种情况下,说明2^4r-1可以被8r+1形式的素数整除,但由于指数4r是偶数,所以这种数不属于梅森数的类型.对于后一种情况,我们的结论是2^4r+3-1可以被形如8r+7的素数整除.   所以当4r+3和8r+7都是素数时,8r+7必能整除相应的梅森数.

　　能满足上述条件的r与n的数值,可以参看下表:

　　当Mp不是素数时,那么肯定另外存在一个素数q>2,使得q-1=sp,而使2^sp-1是q的倍数,从而2^p-1也是q的倍数,由于q-1是偶数,而p是奇数,所以s必是偶数,令s=2k,则有
q=2kp+1,这就是说,形如2^p-1(p是素数)的数具有形如q=2kp+1的因子.利用这一点可以求出梅森数的因子.例如已经知道2¹¹-1是合数,它的因子必然是形如2k*11+1=22k+1的形式,k=1时,得到23,而23果然能够整除2¹¹-1(2¹¹-1=2047=23*89).

　　 已经研究出一些非常巧妙的办法来大大地削减试探的工作量,1876年,法国数学家E.V.卢卡发明了一种测试法检查梅森数的素性.1930年,美国数学家D.H.莱默对此进行了改进,使之非常有效,实用.方法如下:

　　定义数列:u₀=4,u_k+1=u_k²-2 mod Mn  (k=0,1,2...n)

　　若u_k-2=0 mod Mn 则Mn是素数,否则Mn不是素数.有关这个定理的证明可以到素数检验法中找到它.

　　这个检验法是如此简单,以至于两位对此定理还不十分理解的高中生L.尼科尔和C.诺尔经过3年的努力,在1978年利用CYBER174型计算机发现了有6533位数的梅森素数M21701.一年以后,诺尔又一次改写了这个记录,找到了有6987位数的梅森素数M23209.

　　现在寻找很大的梅森素数时,已经完全依赖于计算机了,可以想象,离开了计算机,我们人类将会落入一种怎样的地步.当D.H.莱默博士这位曾经在梅森素数上花费了许多时光的老学者,亲眼看到了计算机在短短的48秒钟内做完了他20年前花费了700多小时才完成的艰辛劳动,最后证明2²⁵⁷-1是一个合数时,他是多么地感慨万端哪.

　　时至今日,人类只找到38个梅森素数.前18个梅森素数是n=2,3,5,7,13,17,19,31,61,89,107,127
,521,607,1279,2203,2281,3217时的Mn=2ⁿ-1.下表列出了从1961年以来所发现的全部梅森素数.摘自http://www.utm.edu/research/primes/