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 everlarger primes of this form.
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 LucasLehmer 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} ≈ 10^{3}, 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.
LucasLehmer Test (LLT)
We define a sequence of numbers L_{k} called the LucasLehmer sequence, as follows:
L_{1} = 4 and L_{n } = (L_{n}_{1})^{2} – 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 LucasLehmer 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 LucasLehmer 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 LucasLehmer 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 highlevel computer language. Much of the computation time is taken up squaring the LucasLehmer 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_{11 } and M_{23} are composite. For example, M_{11} = 2047 = 23*89 and M_{23} = 8388607 = 47*178481.
A more detailed discussion of the LucasLehmer 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.