ThatsMaths

Once again the record for the largest prime number has been shattered. As with all recent records, the new number is a Mersenne prime, a number of the form

M_p = 2^p – 1

where p itself is a prime. Participants in a distributed computing project called GIMPS (Great Internet Mersenne Prime Search) continue without rest to search for ever-larger primes of this form.

Image from http://primes.utm.edu

Most of the recent large primes have been found in the GIMPS project (for an earlier post on GIMPS, click Mersennery Quest. The project uses a search algorithm called the Lucas-Lehmer primality test, which is particularly suitable for finding Mersenne primes. The test, which was originally devised by Edouard Lucas in the nineenth century and extended by Derek Lehmer in 1930, is very efficient on binary computers.

Recently at the University of Central Missouri a mathematics professor, Curtis Cooper, found the new Mersenne prime,

M(74,207,281) = 2^{74 207 281} – 1.

Using the approximation 2¹⁰ ≈ 10³, we can see that it has approximately 22 million decimal digits. The previous record had “only” 17 million digits. The new prime was found last September but, due to email glitches, was not confirmed until 7 January. With 5,000 digits per page, the new record number would require about 4400 pages to print in decimal form.

Mersenne numbers are defined as numbers of the form

M_k = 2^k – 1.

It is simple to show that if k is composite then so is M_k. But if p is a prime, then M_p may or may not be prime too. Prime numbers of the form M_p = 2^p – 1 are called Mersenne primes, and almost all the largest known primes are of this form.

Lucas-Lehmer Test (LLT)

We define a sequence of numbers L_k called the Lucas-Lehmer sequence, as follows:

L₁ = 4 and L_n = (L_n-1)² – 2 for n > 1 .

This rule yields the sequence { 4, 14, 194, 37 634, 1 416 317 954, … } in which the terms rapidly grow. The Lucas-Lehmer Test (LLT) may be stated as a

Theorem: M_p is prime if and only if L_p-1 ≡ 0 mod M_p.

In other words, M_p is prime if and only if M_p divides L_p-1 exactly. The Lucas-Lehmer numbers grow rapidly, and soon break the limits of most computers, but it is sufficient to compute the terms modulo M_p, keeping them within reasonable bounds.

The Lucas-Lehmer Test can be implemented in just a few lines of computer code. The following is a Mathematica version of the test:

This is simple to implement in any other high-level computer language. Much of the computation time is taken up squaring the Lucas-Lehmer numbers repeatedly, but faster algorithms can be used to reduce the computation time drastically.

Some results for the first few values of p are shown in the following table. We see that some of the examples are prime whereas others, M₁₁ and M₂₃ are composite. For example, M₁₁ = 2047 = 23*89 and M₂₃ = 8388607 = 47*178481.

 A more detailed discussion of the Lucas-Lehmer test, and proofs of the results, can be found in standard works on number theory, such as Hardy and Wright. See also the Mersenne Wiki (URL below).

Sources

• Hardy, Godfrey Harold and Wright, E. M. (1960): An introduction to the theory of numbers (Fourth Ed.), Oxford, at the Clarendon Press.

• Mersenne Wiki: The wiki is for the Great Internet Mersenne Prime Search.