# What is it?

The Lucas-Lehmer test is a test to determine the primality of Mersenne numbers, M_{n}=2^{n}-1 and states that M_{p} is prime, if and only if s_{p-2 }is congruent to 0 mod M_{p}. where s_{p} is the sequence defined by s_{i }=s_{i-1}^{2}-2 with s_{0}=4. In other words, calculate the p-2 term of this sequence, and if M_{p} divides it, then you have found a Mersenne prime.

The basis for the test was built by Edouard Lucas in the late 1870’s, and in 1876 he used a rough version of what would become the test to prove that 2^{127} -1 = 170141183460469231731687303715884105727 was prime, which stood as the largest known prime for 75 years, and is the largest prime ever found by hand calculations. However, Lucas was only able to prove the case where p was congruent to 1 mod 4. In the 1930’s Lehmer extended Lucas’s result by showing its truth for all odd primes p and in formulating it into the “Lucas-Lehmer test” which is still used for proving the primality of Mersenne numbers.

# Some examples

The first 7 terms of s_{i} are 4, 14, 194, 37634, 1416317954, 2005956546822746114 and 4023861667741036022825635656102100994, which quite clearly demonstrates how quickly s_{i} grows. Given this speed, simply look at a few somewhat more easily calculable (thought still dubious) cases whose outcome is obvious, M_{3}, M_{4} and M=7=. First M_{3} =2^{3}-1=7 and from this list above s_{1}= 14 and 14 = 2*7, so the test tells us that 7 is prime which is true. Now looking at M_{4}=16-1=15 which is not prime and since, s_{2}=194=13*15-1 the test correctly yields that 15 is not prime. Lastly, looking at a larger example M_{7}=2^{7}-1=127, it is not hard to see that 2,3,5,7 and 11 all do not divide 127 it is clearly a prime. Now performing the test s_{5}= 2005956546822746114 = 127*15794933439549182, which confirms that 127 is prime, however in this case in particular, checking the primes I listed is far far easier than performing division on a 19 digit number by a 3 digit number.

Clearly in these cases, checking by trial and error would be easier than using the test; however, as you check larger and larger M_{p} the number of primes you would need to check starts to become a bit extreme. For example, the smallest number M_{59} is divisible by is 179951 which is the 16336^{th} prime. In cases such as this the Lucas-Lehmer test seems to be quite a bit easier than checking 16336 primes. In an even a less extreme example, M_{13} is 156 digits at which point it seems like, particularly if working without computer assistance, the Lucas-Lehmer test, which requires computing 11 terms and then dividing once, appears to be a better option than trial division which would entail dividing quite a few more times, and that although individually easier to compute, I certainly wouldn’t enjoy.

# Proof

The proof of sufficiency given by J.W. Bruce for the Lucas-Lehmer test is the reason why I find the statement so memorable and actually really cool. While I can’t find how Lehmer originally proved the test, Michael Rosen published a proof in 1988 which the majority of other proofs are simplifications of (including Bruce’s), and though I won’t copy it, I will explain the lemma I find so interesting that the proofs hinge on.

Lemma: Let w=2+√3, v=2-√3 and a=2^{m-2}. Then S_{m} = w^{a}+v^{-a}.

This is shown fairly easily by induction and is then used in the proof to get some useful equalities when assuming M_{p} divides s_{p-2} . The proof then uses these equalities along with the fact that w is a unit in Z[√3] to find a contradiction when looking at the multiplicative group Z[√3]/qZ where q is a prime divisor of M_{p}. I don’t know about anyone else, but when speaking about whether ridiculously large numbers of the form 2^{n}-1 are prime, I find that making the leap from an integer sequence to the ring Z[√3] to be a very non-intuitive step. I think it’s fascinating how much realizing this “strange” relation simplifies a seemingly very complex problem into something very straightforward.

# In Conclusion

Well, I hope the takeaway from this is that if ever someone needs to figure out if a 100+digit number of the form 2^{n}-1 is prime and you don’t have access to the internet (or similar resource), you now have a way to do it without determining a lot of primes up to it and dividing a bunch of times. Though really in all seriousness, I hope I’ve given a reasonable explanation to what the Lucas-Lehmer test is and why it’s so useful and I hope that anyone reading this (yeah right) will take a look at Rosen’s and Bruce’s proofs as they are really quite cool (even bigger yeah right).

# Sources:

Rosen’s proof of the entire test: http://www.jstor.org/stable/2322904

Bruce’s Proof of Sufficiency: http://www.jstor.org/stable/2324959

http://primes.utm.edu/notes/by_year.html

http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test

http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test