Proof of Sufficiency.
Suppose 2p - 1 divides Sp-1.
Let
w = 2 + sqrt(3) and v = 2 - sqrt(3).
Then by induction on n,
Sn = w2n-1 + v2n-1.
Since 2p - 1 divides Sp-1,
w2p-2 + v2p-2 = R
Mp .
Multiplying both sides by w2p-2, we obtain
(1) w2p-1 = R Mp w2p-2
- 1 .
Squaring both sides yields
(2) w2p = (R Mp w2p-2
- 1)2 .
Now we proceed by contradiction.
Suppose Mp is not prime.
Choose one of its prime divisors
q that is not greater than its square root.
Consider the group G = Zq ( sqrt(3) )* of all the
numbers a + b sqrt(3) modulo q which are invertible.
Note that G has at
most q2 - 1 elements.
Viewing (1) and (2) mod q, we have
w2p-1 = -1 (mod q)
and
w2p = 1 (mod q).
Thus, w is an element of G with order 2p.
Since the order of
an element is at most the order of the group we have
2p <= q2 - 1 < Mp = 2p
-1 ,
a contradiction.
This completes the proof.