PROOF OF SUFFICIENCY OF LUCAS-LEHMER TEST Suppose 2^{p} − 1 divides S_{p−1}. Let w = 2 + \sqrt{3} and v = 2 − \sqrt{3}. Then, by induction on n,

S_{n} = w^{2^{n−1}} + v^{2^{n−1}}.

Since 2^{p} − 1 divides S_{p−1},

w^{2^{p−2}} + v^{2^{p−2}} = RM_{p}.

Multiplying both sides by

w^{2^{p−2}},

we obtain

w^{2^{p−1}} = RM_{p}w^{2^{p−2}} − 1.  (1)

Squaring both sides yields

w^{2^{p}} = (RM_{p}w^{2^{p−2}} − 1)^{2}.  (2)

Now we proceed by contradiction. Suppose M_{p} is not prime. Choose one of its prime divisors q that is not greater than its square root. Consider the group G = ℤ_{q}(\sqrt{3})^{∗} of all the numbers a + b\sqrt{3} modulo q which are invertible. Note that G has at most q^{2} − 1 elements. Viewing (1) and (2) mod q, we have

w^{2^{p−1}} = −1 (mod q) and w^{2^{p}} = 1 (mod q).

Thus, w is an element of G with order 2^{p}. Since the order of an element is at most the order of the group we have

2^{p} ≤ q^{2} − 1 < M_{p} = 2^{p} − 1,

a contradiction. This completes the proof.