卢卡斯-莱默检验法原理是这样:
令梅森数
Mp = 2p− 1作为检验对象(预设p是素数,否则Mp就是合数了)。
定义序列{si }:所有的i ≥ 0
|
,如果 ;
|
,如果 。
|
- .
- .
- .
这个序列的开始几项是4, 14, 194, 37634, ... (OEIS数列A003010)
那么Mp是素数当且仅当
-
否则, Mp是合数。
sp − 2模Mp的余数叫做p的卢卡斯-莱默余数。
我们注意到 是一个具有闭式解的递推关系。定义 及 ;我们可以用数学归纳法来验证对于所有i,都有 :
- 。
-
最后一个步骤可从 推出。在两个部分中,我们都将用到这个结果。
充分性
我们希望证明 意味着 是素数。我们叙述一个利用初等群论的证明,由J. W.布鲁斯给出[2]。
假设 。那么对于某个整数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的证明[3]。首先,注意到3是模 Mp的二次非剩余,这是因为对于奇数p > 1,2 p − 1只取得值7 mod 12,因此从勒让德符号的性质可知 是−1。根据欧拉准则,可得:
- .
另一方面,2是模 的二次剩余,这是因为 ,因此 。根据欧拉准则,可得:
- .
接着,定义 ,并像前面那样,定义X*为 的乘法群。我们将用到以下的引理:
-
(根据费马小定理),以及
-
对于所有整数a(费马小定理)。
那么,在群X*中,我们有:
-
简单计算可知 。我们可以用这个结果来计算群X*中的 :
-
其中我们用到了以下的事实:
- 。
由于 ,我们还需要做的就是把方程的两边乘以 ,并利用 :
-
由于sp−2是整数,且在X*内是零,因此它也是零mod Mp。