卢卡斯-莱默检验法

卢卡斯-莱默检验法（），是数学中检验梅森数的素性检验，由法國數學家爱德华·卢卡斯（）于1878年完善，美國數學家德里克·亨利·莱默（）随后于1930年代将其改进。

因特网梅森質数大搜索用这个检验法找到了不少很大的質数，最近几个最大的質数就是这个项目发现的。GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what 由于梅森数比随机选择的整数更有可能是質数，因此他们认为这是一个极有用的方法。

方法

卢卡斯－莱默检验法原理是这样：
令梅森数
Mp = 2p− 1作为检验对象（预设p是質数，否则Mp就是合数了）。

定义序列{si }：所有的i ≥ 0 
{| align=left border="0"
|rowspan=2| 
| ，如果；
|-
| ，如果。
|}
.
.
.

这个序列的开始几项是4, 14, 194, 37634, ... 

那么Mp是素数当且仅当

否则, Mp是合数。
sp − 2模Mp的余数叫做p的卢卡斯－莱默余数。

例子

假设我们想验证M3 = 7是素数。我们从s=4开始，并更新3−2 = 1次，把所有的得数模7：

 s ← ((4×4) − 2) mod 7 = 0

由于我们最终得到了一个能被7整除的s，因此M3是素数。

另一方面，M11 = 2047 = 23×89就不是素数。我们仍然从s=4开始，并更新11−2 = 9次，把所有的得数模2047：

 s ← ((4×4) − 2) mod 2047 = 14
 s ← ((14×14) − 2) mod 2047 = 194
 s ← ((194×194) − 2) mod 2047 = 788
 s ← ((788×788) − 2) mod 2047 = 701
 s ← ((701×701) − 2) mod 2047 = 119
 s ← ((119×119) − 2) mod 2047 = 1877
 s ← ((1877×1877) − 2) mod 2047 = 240
 s ← ((240×240) − 2) mod 2047 = 282
 s ← ((282×282) − 2) mod 2047 = 1736

由于s最终仍未能被2047整除，因此M11=2047不是素数。但是，我们从这个检验法仍然无法知道2047的因子，只知道它的卢卡斯-莱默余数1736。

正确性的证明

我们注意到是一个具有闭式解的递推关系。定义及；我们可以用数学归纳法来验证对于所有i，都有：

。

最后一个步骤可从推出。在两个部分中，我们都将用到这个结果。

充分性

我们希望证明意味着是素数。我们叙述一个利用初等群论的证明，由J. W.布鲁斯给出J. W. Bruce. A Really Trivial Proof of the Lucas-Lehmer Test. The American Mathematical Monthly, Vol.100, No.4, pp.370–371. April 1993.。

假设。那么对于某个整数k，有，以及：

现在假设Mp是合数，其非平凡素因子q > 2（所有梅森素数都是奇数）。定义含有q2个元素的集合，其中是模q的整数，是一个有限域。X中的乘法运算定义为：

.

由于q > 2，因此和位于X内。任何两个位于X内的数的乘积也一定位于X内，但它不是一个群，因为不是所有的元素x都有逆元素y，使得xy = 1。如果我们只考虑有逆元素的元素，我们便得到了一个群X*，它的大小最多为（因为0没有逆元素）。

现在，由于，且，我们有，根据方程(1)可得。两边平方，得，证明了是可逆的，其逆元素为，因此位于X*内，它的目能整除。实际上，这个阶必须等于，因为，因此这个阶不能整除。由于群元素的阶最多就是群的大小，我们便得出结论，。但由于q是的一个非平凡素因子，我们必须有，得出矛盾。因此是素数。

必要性

我们假设是素数，欲推出。我们叙述一个Öystein J. R.
Ödseth的证明Öystein J. R. Ödseth. A note on primality tests for N = h · 2n − 1. Department of Mathematics, University of Bergen. http://www.uib.no/People/nmaoy/papers/luc.pdf 。首先，注意到3是模 Mp的二次非剩余，这是因为对于奇数p > 1，2 p − 1只取得值7 mod 12，因此从勒让德符号的性质可知是−1。根据欧拉准则，可得：

 .

另一方面，2是模的二次剩余，这是因为，因此。根据欧拉准则，可得：

 .

接着，定义，并像前面那样，定义X*为的乘法群。我们将用到以下的引理：



（根据费马小定理），以及



对于所有整数a（费马小定理）。

那么，在群X*中，我们有：

简单计算可知  。我们可以用这个结果来计算群X*中的：

其中我们用到了以下的事实：

 。

由于，我们还需要做的就是把方程的两边乘以，并利用：



由于sp−2是整数，且在X*内是零，因此它也是零mod Mp。

参见
梅森素数
因特网梅森素数大搜索（GIMPS）
新梅森猜想
埃拉托斯特尼筛法
米勒-拉宾检验
试除法
费马素性检验
卢卡斯-莱默检验法
孪生素数
三胞胎素数
四胞胎素数
素数判定法则
表兄弟素数
六素数
X²+1素数

注释

参考文献
  Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

 外部链接 

 GIMPS (The Great Internet Mersenne Prime Search)
 A proof of Lucas–Lehmer–Reix test (for Fermat numbers) 
 Lucas–Lehmer test at MersenneWiki

Category:素性测试
Category:梅森素数