proof of Lucas-Lehmer primality test

The objective of this article is to prove the Lucas-Lehmer primality test:
Let p>2 be a prime, and let Mp=2p-1 be the corresponding Mersenne number. Then Mp is prime if and only if Mp divides sp-1 (equivalently, if and only if sp-10(Mp)) where the numbers (sn)n1 are given by the following recurrence relation:

s1 =4
sn+1 =sn2-2,n1

We show that the validity of the primality test is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to the following theorem, which is then proved directly:

Theorem 1.

(Lucas) Mp is prime if and only if α(Mp+1)/2-1(Mp), where α=2+3.

To see that the two are in fact equivalent, let β=2-3. Then α+β=4,αβ=1. Thus

s1 =α+β
s2 =(α+β)2-2=α2+β2+2αβ-2=α2+β2
s3 =α4+β4
sp-1 =α2p-2+β2p-2

Note that 2p-2=Mp+14. Then

sp-10(Mp) α(Mp+1)/4+β(Mp+1)/40(Mp)

It thus remains to prove Theorem 1. We start with two simple lemmas:

Lemma 2.

If p>3 is prime, then αp-11(p) or αp+11(p).

αp2p+3(p-1)/23{α(p)if (3p)=1β(p)if (3p)=-1

where () is the Legendre symbolMathworldPlanetmath. Thus


Lemma 3.

Let p be a prime with p7(8) and p7(12). Then α(p+1)/2-1(p).


(1+3)2=4+23=2α, so that


But p7(8), so that (2p)=1. Thus 2(p+1)/222(p-1)/22(p) and therefore




But p7(12), so 3(p-1)/2-1(p) and thus


Putting together the two expressions for (1+3)p+1, we get α(p+1)/2-1(p). ∎

We are now in a position to prove Theorem 1:


(): If Mp is prime where p>3 is prime, then note that Mp7(8),7(1)2 so that Mp satisfies the conditions of Lemma 3. The result follows.

(): If α(Mp+1)/2-1(Mp), choose qMp for q a prime. Since Mp7(1)2, we have q>3. Since α(Mp+1)/2-1(Mp) also α(Mp+1)/2-1(q) and thus αMp+11(q). But Mp+1=2p, so


Thus the order of α(q) divides 2n. It can’t divide 2n-1 since α(Mp+1)/2-1(q), so its order is precisely 2n=Mp+1. However, αq+11(q) or αq-11(q) by Lemma 2 and thus qMp. But qMp, so q=Mp and Mp is in fact prime. ∎

Title proof of Lucas-Lehmer primality test
Canonical name ProofOfLucasLehmerPrimalityTest
Date of creation 2013-03-22 18:42:16
Last modified on 2013-03-22 18:42:16
Owner rm50 (10146)
Last modified by rm50 (10146)
Numerical id 5
Author rm50 (10146)
Entry type Proof
Classification msc 11A51