Tag Archives: prime numbers

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/

Numbers Courtesy of Fermat and Mersenne

A portrait of Pierre de Fermat, lawyer and amateur mathematician. Image: Author and painter unknown, via Wikimedia Commons.

It is not often a person contributes to a field they do not even work in the way Pierre de Fermat has contributed to the field of mathematics. Born to a wealthy leather merchant, Fermat received a bachelor’s in civil law from the University of Orléans and went on to become a lawyer, while at the same time engraving his name into math history books, doing said math just for recreation. His importance in mathematics lead to many theorems named after him, as well as numbers. These numbers are known as Fermat numbers, which are positive integers, that take of the form Fn = 2(2n) + 1, when n is nonnegative and an integer. For example for F1, F1= 2(2)+1= 5. The first five Fermat numbers are 3, 5, 17, 257, and 65537, and these numbers continue to grow to incredibly large magnitudes. Fermat believed this form created an infinite number of prime numbers, which are known as Fermat primes.

Fermat numbers are occasionally written as 2n+1, but since when n is greater than zero and Fn prime, n must be a power of two, the form Fn = 2(2n) + 1 is the common form for Fermat numbers. One of the main problems with Fermat claiming all these numbers are prime is the fact that they soon become too large to calculate for even today’s computers, let alone a man with his pen and paper in the 17th century. Unfortunately for Fermat, by the time the 18th century rolled around, he was dead. In 1732, mathematician Leonhard Euler found that F5, which is 4,294,967,297, is actually divisible by 641, most likely figuring this out from having a large amount of time on his hands. While this showed that some Fermat numbers are not actually prime, excluding when n=0 in the form 2n+1, it does not discount the fact that the Fermat number equation could still make an infinite number of primes, since there are infinite amount of Fermat numbers. However as of now, the only Fermat primes that are known are F0 through F4.

Now initially I found the idea of an equation, the equation here being Fn = 2(2n) + 1, that finds only certain prime numbers, most of which are way too large to even be calculated even 400 years after the equation for them was created, the equivalent to a student doing extra credit when he has a 98% in his class. What I’m trying to say is, I found Fermat numbers pointless and to be the 17th century mathematician’s version of a braggadocio. However, I know nothing and Gauss managed to find a relationship between “Euclidean construction of regular polygons and Fermat primes,” where he showed a regular 17-gon could be constructed. It was also found a regular n-gon can be created if n is the product of any number of Fermat primes and the number 2. These regular n-gons take the property of being able to be constructed with a compass and straightedge. Who would have thought one of the greatest mathematicians to ever live could leave me feeling so inadequate, at least mathematically.

Similar to Fermat numbers are what are known Mersenne numbers, created by 17th century French mathematician and music theorist Marin Mersenne. Yet again a person being a jack of all trades, except instead of being a master of none they were a master of a few or at least of one. Mersenne numbers take of the form Mn = 2n -1, and Mersenne primes are numbers that take that form which are prime. Mersenne believed that for n<=257, Mn was prime for n= 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257, and the rest are composite. While this belief turned out to incorrect, he still got the name for the primes. Just like Fermat primes, it is unknown whether there are an infinite number of Mersenne primes, but as of now 48 Mersenne primes are known, the largest being 257885161-1, which again makes me wonder how much time do some of these mathematicians have on their hands.

Mersenne numbers were originally studied because of their connection to perfect numbers, which are positive integers that are equal to the sum of their divisors. Euclid proved that if the number 2n-1 is prime, then 2n-1(2n-1) is a perfect number, which many years later led to Euler discovering that all even perfect numbers come in this form. Another interesting fact is that the ten largest known prime numbers are Mersenne numbers. I personally find number theory incredibly interesting, partly because I like numbers and partly because how mathematicians are able to come with these theorems and proofs baffle me. I ultimately wonder if they had any true goals when thinking about these primes, or if it was just for the pure fun and interest in it.

References:

http://en.wikipedia.org/wiki/Fermat_number

http://interact.sagemath.org/edu/2010/414/projects/tsang.pdf

http://mathworld.wolfram.com/FermatNumber.html

http://mathworld.wolfram.com/FermatPrime.html

https://primes.utm.edu/glossary/page.php?sort=FermatNumber

http://en.wikipedia.org/wiki/Mersenne_prime

http://en.wikipedia.org/wiki/Marin_Mersenne

http://en.wikipedia.org/wiki/Pierre_de_Fermat

http://mathworld.wolfram.com/MersennePrime.html