Lucas-Lehmer Test
Definition. Let
S
1
= 4
and
S
n+1
= S
n
2
- 2 for n >= 1.
Lucas-Lehmer Test.
Let p be a prime number. Then,
M
p
= 2
p
-1 is prime
if and only if
M
p
divides S
p-1
.
Proof of Sufficiency