Proof of Sufficiency.
Let S₁ = 4 and S_n+1 = S_n² - 2, for n >= 1.
Let w = 2 + sqrt(3) and v = 2 - sqrt(3). Then by induction on n we can show that S_n = w^2n-1 + v^2n-1. Assuming M_p = 2^p - 1 divides S_p-1, it follows that w^2p-2 + v^2p-2 = S_p-1 = R M_p . Multiplying both sides by w^2p-2 and using the fact that wv = 1, we obtain (1) w^2p-1 = R M_p w^2p-2 - 1 . Squaring both sides yields (2) w^2p = (R M_p w^2p-2 - 1)² . 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 = Z_q ( sqrt(3) )^* of all the numbers a + b sqrt(3) modulo q which are invertible. Note that G has at most q² - 1 elements.

Viewing (1) and (2) mod q, we have w^2p-1 = -1 (mod q) and w^2p = 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² - 1 < M_p = 2^p -1 , a contradiction.