メルセンヌ数
p が奇素数のとき、S0 = 4, Sn = Sn−1 − 2 (n ≥ 1) で{Sn} を定義すると、
M p ∤ S k ( 0 ≦ k ≦ p − 2 ) {\displaystyle M_{p}\not \mid S_{k}\ (0\leqq k\leqq p-2)} ならば、Mp は合成数である
M p ∣ S p − 2 {\displaystyle M_{p}\mid S_{p-2}} ならば、Mp は素数である
リュカ–レーマー・テストは二進計算機用のアルゴリズムに向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2 ≡ 1 (mod Mp) より、A·2 + B ≡ A + B (mod Mp) が成り立つので、Mp で割る割り算の代わりに、二進法で p 桁のシフト演算と足し算だけで計算できる。
アルゴリズム
アルゴリズムは以下の擬似コードで表される。