方法

卢卡斯－莱默检验法原理是这样：令梅森数 Mp = 2− 1作为检验对象（预设p是素数，否则Mp就是合数了）。定义序列{si }：所有的i ≥ 0

这个序列的开始几项是4,14,194, 37634, ... （OEIS中的数列A003010） 那么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。

正确性的证明

我们注意到⟨ ⟨ -->si⟩ ⟩ -->{\displaystyle {\langle }s_{i}{\rangle }}是一个具有闭式解的递推关系。定义ω ω -->=2+3{\displaystyle \omega =2+{\sqrt {3}}}及ω ω -->¯ ¯ -->=2− − -->3{\displaystyle {\bar {\omega }}=2-数学归纳法t {3}}}；我们可以用数学归纳法来验证对于所有i，都有si=ω ω -->2i+ω ω -->¯ ¯ -->2i{\displaystyle s_{i}=\omega ^{2^{i}}+{\bar {\omega }}^{2^{i}}}：

最后一个步骤可从ω ω -->ω ω -->¯ ¯ -->=(2+3)(2− − -->3)=1{\displaystyle \omega {\bar {\omega }}=(2+{\sqrt {3}})(2-{\sqrt {3}})=1}推出。在两个部分中，我们都将用到这个结果。

充分性

我们希望证明sp− − -->2≡ ≡ -->0(modMp){\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}意味着Mp{\displaystyle M_{p}}是素数。我们叙述一个利用初等群论的证明，布鲁斯 W.布鲁斯给出。

假设sp− − -->2≡ ≡ -->0(modMp){\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}。那么对于某个整数k，有ω ω -->2p− − -->2+ω ω -->¯ ¯ -->2p− − -->2=kMp{\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kM_{p}}，以及：

现在假设Mp是合数，其非平凡素因子q > 2（所有梅森素数都是奇数）。定义含有q个元素的集合X={a+b3|a,b∈ ∈ -->Zq}{\displaystyle X=\{a+b{\sqrt {3}}|a,b\in \mathbb {Z} _{q}\}}，其中Zq{\displaystyle \mathbb {Z} _{q}}是模q的有限域是一个有限域。X中的乘法运算定义为：

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

现在，由于Mp≡ ≡ -->0(modq){\displaystyle M_{p}\equiv 0{\pmod {q}}}，且ω ω -->∈ ∈ -->X{\displaystyle \omega \in X}，我们有kMpω ω -->2p− − -->2=0{\displaystyle kM_{p}\omega ^{2^{p-2}}=0}，根据方程(1)可得ω ω -->2p− − -->1=− − -->1{\displaystyle \omega ^{2^{p-1}}=-1}。两边平方，得ω ω -->2p=1{\displaystyle \omega ^{2^{p}}=1}，证明了ω ω -->{\displaystyle \omega }是可逆的，其逆元素为ω ω -->2p− − -->1{\displaystyle \omega ^{2^{p}-1}}，因此位于X*内，它的目能整除2p{\displaystyle 2^{p}}。实际上，这个阶必须等于2p{\displaystyle 2^{p}}，因为ω ω -->2p− − -->1≠ ≠ -->1{\displaystyle \omega ^{2^{p-1}}\neq 1}，因此这个阶不能整除2p− − -->1{\displaystyle 2^{p-1}}。由于群元素的阶最多就是群的大小，我们便得出结论，2p≤ ≤ -->q2− − -->1Mp=2p− − -->1{\displaystyle q^{2}\leq M_{p}=2^{p}-1}，得出矛盾2p1{\displaystyle 2^{p}<2^{p}-1}。因此Mp{\displaystyle M_{p}}是素数。

必要性

我们假设Mp{\displaystyle M_{p}}是素数，欲推出sp− − -->2≡ ≡ -->0(modMp){\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}。我们叙述一个Öystein J. R. Ödseth的证明。首先，注意到3是模 Mp的二次非剩余，这是因为对于奇数p > 1，2 − 1只取得值7 m勒让德符号，因此从勒让德符号的性质可知(3|Mp){\displaystyle (3|M_{p欧拉}是−1。根据欧拉准则，可得：

另一方面，2是模Mp{\displaystyle M_{p}}的二次剩余，这是因为2p≡ ≡ -->1(modMp){\displaystyle 2^{p}\equiv 1{\pmod {M_{p}}}}，因此2≡ ≡ -->2p+1=(2(p+1)/2)2(modMp){\displaystyle 2\equiv 2^{p+1}=\left(2^{(p+1)/2}\right)^{2}{\pmod {M_{p}}}}。根据欧拉准则，可得：

接着，定义σ σ -->=23{\displaystyle \sigma =2{\sqrt {3}}}，并像前面那样，定义X*为{a+b3|a,b∈ ∈ -->ZMp}{\displaystyle \{a+b{\sqrt {3}}|a,b\in \mathbb {Z} _{M_{p}}\}}的乘法群。我们引理到以下的引理：

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

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

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

简单计算可知 ω ω -->=(6+σ σ -->)2/24{\displaystyle \omega =(6+\sigma )^{2}/24}。我们可以用这个结果来计算群X*中的ω ω -->(Mp+1)/2{\displaystyle \omega ^{(M_{p}+1)/2}}：

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

由于Mp≡ ≡ -->3(mod4){\displaystyle M_{p}\equiv 3{\pmod {4}}}，我们还需要做的就是把方程的两边乘以ω ω -->¯ ¯ -->(Mp+1)/4{\displaystyle {\bar {\omega }}^{(M_{p}+1)/4}}，并利用ω ω -->ω ω -->¯ ¯ -->=1{\displaystyle \omega {\bar {\omega }}=1}：

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

参见

梅森素数

因特网梅森素数大搜索（GIMPS）

新梅森猜想

埃拉托斯特尼筛法

米勒-拉宾检验

试除法

费马素性检验

参考文献

Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective t edition. Springer. 2001. ISBN 978-0-387-94777-8. 引文格式1维护：冗余文本 (link) Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。