# Lucas-Lehmer test (proof)

• Jun 21st 2010, 07:15 AM
jamix
Lucas-Lehmer test (proof)
Recall the Lucas Lehmer primality test for Mersenne primes which claims the following:

$\displaystyle 2^p - 1$ is prime iff $\displaystyle s_{p-1} \equiv 0 mod{p}$

where $\displaystyle s_1 = 4$ and $\displaystyle s_i \equiv s_{i-1}^2 - 2 mod{p}$.

Does anyone know the details to the proof of this important theorem? I've been trying to work it out on my own, but its tough.
• Jun 21st 2010, 07:16 AM
chiph588@
• Jun 21st 2010, 09:53 AM
jamix
The proof on wiki was much easier to follow than many others I've seen, thanks. Who would have though that one could consider the orders of elements in the integral domain $\displaystyle Z_p + Z_p \cdot \sqrt{3}$ in order to solve this!?

Thanks again.
• Jun 21st 2010, 05:26 PM
jamix
I'm finding that for prime Mersennes $\displaystyle q = 2^p - 1$, one doesn't necessarily need to have $\displaystyle s_0 = 4$ in order for $\displaystyle s_{p-2} \equiv 0 mod(q)$.

Consider the prime $\displaystyle 2^7 - 1$ for instance. If $\displaystyle s_0$ is in the following set we have that $\displaystyle s_{p-2} \equiv 0 mod(q)$.

{3,4,10,18,21,27,37,38,43,44,46,49,51,52,54,63,64, 73,75,76,78,81,83,84,89,90,100,106,109,117,123,124 }

I'm guessing there is a probalistic reason for this occurence. Anyone wanna try to work through it with me?