The Lucas-Lehmer Test and Why It’s Pretty Neat

What is it?

The GIMPS Logo. Public domain, via Wikimedia Commons.

The GIMPS Logo. Public domain, via Wikimedia Commons.

The Lucas-Lehmer test is a test to determine the primality of Mersenne numbers, Mn=2n-1 and states that Mp is prime, if and only if sp-2 is congruent to 0 mod Mp. where sp is the sequence defined by s­i =si-12-2  with s0=4. In other words, calculate the p-2 term of this sequence, and if Mp 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 2127 -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 si are 4, 14, 194, 37634, 1416317954, 2005956546822746114 and 4023861667741036022825635656102100994, which quite clearly demonstrates how quickly si grows.  Given this speed, simply look at a few somewhat more easily calculable (thought still dubious) cases whose outcome is obvious, M3, M4 and M=7=. First M­­3 =23-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 M4=16-1=15 which is not prime and since, s2=194=13*15-1 the test correctly yields that 15 is not prime. Lastly, looking at a larger example M7=27-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 Mp the number of primes you would need to check starts to become a bit extreme. For example, the smallest number M59 is divisible by is 179951 which is the 16336th 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, M13 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=2m-2. Then Sm = wa+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 sp-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 2n-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 2n-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

http://primes.utm.edu/mersenne/

Advertisements