# 卢卡斯-莱默检验法

## 方法

 ${\displaystyle s_{i}={\begin{cases}\;\;\,4\\s_{i-1}^{2}-2\end{cases}}}$ ，如果${\displaystyle \displaystyle i=0}$ ； ，如果${\displaystyle \displaystyle i>0}$ 。
.
.
.

${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}};}$

sp − 2Mp的余数叫做p卢卡斯－莱默余数

## 例子

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

• 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

## 正确性的证明

${\displaystyle s_{0}=\omega ^{2^{0}}+{\bar {\omega }}^{2^{0}}=(2+{\sqrt {3}})+(2-{\sqrt {3}})=4}$
${\displaystyle {\begin{array}{lcl}s_{n}&=&s_{n-1}^{2}-2\\&=&\left(\omega ^{2^{n-1}}+{\bar {\omega }}^{2^{n-1}}\right)^{2}-2\\&=&\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}}+2(\omega {\bar {\omega }})^{2^{n-1}}-2\\&=&\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}},\\\end{array}}}$

### 充分性

${\displaystyle {\begin{array}{rcl}\omega ^{2^{p-2}}&=&kM_{p}-{\bar {\omega }}^{2^{p-2}}\\\left(\omega ^{2^{p-2}}\right)^{2}&=&kM_{p}\omega ^{2^{p-2}}-(\omega {\bar {\omega }})^{2^{p-2}}\\\omega ^{2^{p-1}}&=&kM_{p}\omega ^{2^{p-2}}-1.\quad \quad \quad \quad \quad (1)\\\end{array}}}$

${\displaystyle (a+b{\sqrt {3}})(c+d{\sqrt {3}})=[(ac+3bd){\hbox{ mod }}q]+[(bc+ad){\hbox{ mod }}q]{\sqrt {3}}}$ .

### 必要性

${\displaystyle 3^{(M_{p}-1)/2}\equiv -1{\pmod {M_{p}}}}$ .

${\displaystyle 2^{(M_{p}-1)/2}\equiv 1{\pmod {M_{p}}}}$ .

${\displaystyle (x+y)^{M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod {M_{p}}}}$

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

${\displaystyle a^{M_{p}}\equiv a{\pmod {M_{p}}}}$

${\displaystyle {\begin{array}{lcl}(6+\sigma )^{M_{p}}&=&6^{M_{p}}+(2^{M_{p}})({\sqrt {3}}^{M_{p}})\\&=&6+2(3^{(M_{p}-1)/2}){\sqrt {3}}\\&=&6+2(-1){\sqrt {3}}\\&=&6-\sigma .\end{array}}}$

${\displaystyle {\begin{array}{lcl}\omega ^{(M_{p}+1)/2}&=&(6+\sigma )^{M_{p}+1}/24^{(M_{p}+1)/2}\\&=&(6+\sigma )^{M_{p}}(6+\sigma )/(24\times 24^{(M_{p}-1)/2})\\&=&(6-\sigma )(6+\sigma )/(-24)\\&=&-1.\end{array}}}$

${\displaystyle 24^{(M_{p}-1)/2}=(2^{(M_{p}-1)/2})^{3}(3^{(M_{p}-1)/2})=(1)^{3}(-1)=-1}$

${\displaystyle {\begin{array}{rcl}\omega ^{(M_{p}+1)/2}{\bar {\omega }}^{(M_{p}+1)/4}&=&-{\bar {\omega }}^{(M_{p}+1)/4}\\\omega ^{(M_{p}+1)/4}+{\bar {\omega }}^{(M_{p}+1)/4}&=&0\\\omega ^{(2^{p}-1+1)/4}+{\bar {\omega }}^{(2^{p}-1+1)/4}&=&0\\\omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}&=&0\\s_{p-2}&=&0.\\\end{array}}}$

## 注释

1. ^ GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what页面存档备份，存于互联网档案馆
2. ^ 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.
3. ^ Ö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页面存档备份，存于互联网档案馆