Lucas-Lehmer test (proof)

**jamix** · June 21st 2010, 07:15 AM

Recall the Lucas Lehmer primality test for Mersenne primes which claims the following:

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

where $s_1 = 4$ and $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.

**chiph588@** · June 21st 2010, 07:16 AM

http://en.wikipedia.org/wiki/Lucas–L...of_correctness

**jamix** · June 21st 2010, 09:53 AM

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 $Z_p + Z_p \cdot \sqrt{3}$ in order to solve this!?

Thanks again.

**jamix** · June 21st 2010, 05:26 PM

I'm finding that for prime Mersennes $q = 2^p - 1$ , one doesn't necessarily need to have $s_0 = 4$ in order for $s_{p-2} \equiv 0 mod(q)$ .

Consider the prime $2^7 - 1$ for instance. If $s_0$ is in the following set we have that $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?

Thread: Lucas-Lehmer test (proof)

LinkBack

Thread Tools

Display

Lucas-Lehmer test (proof)

Similar Math Help Forum Discussions

Ironing out the Lucas Primality Test proof

Proof about Fibonacci and Lucas numbers (GCD)

Subspace Test Proof (of test not subset)

Lucas Numbers

Lucas Number Proof By Induction

Search Tags