PROOF OF THE NECESSITY OF LUCAS-LEHMER TEST From M. I. Rosen, “A Proof of the Lucas-Lehmer Test,” American Mathemat-

ical Monthly, 81 (1988), 855–856.

Before giving the proof we need a few definitions. Let

τ = \frac{1 + \sqrt{3}}{\sqrt{2}}, \overline{τ} = \frac{1 − \sqrt{3}}{\sqrt{2}}, ω = τ^{2} = 2 + \sqrt{3}, and \overline{ω} = \overline{τ}^{2} = 2 − \sqrt{3}.

Note that τ\overline{τ} = −1 and ω\overline{ω} = 1.

\underline{Lemma 2}. If we assume M_{p} is prime, then

τ^{M_{p}+1} ≡ −1 (mod M_{p}).

\underline{Proof}. The congruence is understood to take place in the ring of algebraic integers. We temporarily set q = M_{p}.

Write \sqrt{2}τ = 1 + \sqrt{3}, raise both sides to the qth power and take congruences modulo q. We find

τ^{q}2^{(q−1)/2}\sqrt{2} ≡ 1 + 3^{(q−1)/2}\sqrt{3} (mod q).

Since q ≡ −1 (mod 8) we have

2^{(q−1)/2} ≡ (\frac{2}{q}) ≡ 1 (mod q).

Since q ≡ 1 (mod 3) we have

3^{(q−1)/2} ≡ (\frac{3}{q}) ≡ −1 (mod q).

It follows that

τ^{q} ≡ \overline{τ} (mod q) and τ^{q+1} ≡ τ\overline{τ} ≡ −1 (mod q).

We can prove the necessary part of the Lucas-Lehmer Test.

Suppose M_{p} is prime. From Lemma 2 we have

τ^{M_{p}+1} ≡ −1 (mod M_{p}) and τ^{2^{p}} + 1 ≡ 0 (mod M_{p}).

Since τ^{2} = ω,

ω^{2^{p−1}} + 1 ≡ 0 (mod M_{p}).

Multiply both sides of this congruence with

\overline{ω}^{2^{p−1}}

and recall ω\overline{ω} = 1. The result is

S_{p−1} = ω^{2^{p−2}} + \overline{ω} ≡ 0 (mod M_{p}).