A New Largest Prime

Prime numbers -- the positive integers that are only evenly divisible by themselves and one -- are the multiplicative building blocks of the integers. The "fundamental theorem of arithmetic", proved by Gauss in 1801, states that every positive integer can be written as the product of primes in exactly one way (up to reordering of the factors). For example, 1001 is 7 x 11 x 13, and each of the factors are primes, and there is no other way to write 1001 as a product of primes, other than trivial rearrangements such as 11 x 7 x 13. Note that 1 is not a prime number; it is the "empty product" of no prime factors, and it's called a "unit" by mathematicians. There are 25 primes less than 100:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89, and 97.

Prime numbers have attracted a lot of attention throughout mathematical history. As long ago as 250 B.C.E., Eratosthenes gave a method for determining all the primes less than a given limit, now known as the sieve of Eratosthenes. Write down the numbers down from 2 up to n. Circle the number 2. Now cross off every second number after 2: 4, 6, 8, etc. Look for the smallest uncrossed-off, uncircled number. It is 3. Circle it, and cross off every thrid number after 3: 6 (which was crossed off earlier), 9, 12, etc. Now again look for the smallest uncrossed-off, uncircled number. It is 5. Continuing in this fashion, we get a list of all the primes up to n.

In recent years, there has been lot of progress in understanding the primes. For example, in 2002, Agrawal, Kayal, and Saxena found a very efficient method of determining whether a number is a prime. It runs in polynomial time; that is, the number of steps to determine if a number n is prime is bounded by a polynomial in the number of digits of n. And just this year (correcting two previous versions that were incorrect), Goldston, Motohashi, Pintz, and Yildririm proved that the smallest possible gap between a prime p and the next-larger prime grows more slowly than log p. This is a small step towards proving the "twin prime conjecture", which says that there are infinitely many primes p such that p+2 is also prime.

Despite this progress, many open problems about the primes remain. For example, while it is known that there are infinitely many prime numbers, no one knows if there are infinitely many primes of the form 2^p - 1. These are called Mersenne primes, after the 17th century French priest who studied these primes (and made some incorrect claims about them.) Mersenne primes are interesting because they are particularly easy to test for primality, and because of their relationship to an historical problem in number theory, the perfect number problem.

A positive integer is perfect if the sum of its divisors is equal to twice the number. For example, the divisors of 6 are 1, 2, 3, and 6, and they sum to 12, which is twice 6. No one knows currently if there are infinitely many perfect numbers, but Euclid (around 300 B.C.E.) noted that if 2^p - 1 is a prime number, then (2^p - 1)2^p-1 is perfect, and Euler proved that all even perfect numbers are of this form. No odd perfect numbers are known, but there is still no proof that none exists.

Now a new Mersenne prime has been found: 2^30402457-1. This immense number of 9,152,052 digits was discovered by Curtis Cooper and Steven Boone at Central Missouri State. This is the largest known prime number and the 43rd known Mersenne prime.

To get some idea of the recent progress in finding Mersenne primes, when my book Algorithmic Number Theory was published in 1996, we included a table of the largest primes known throughout history. We stopped with 2⁸⁵⁹⁴³³-1, the 33rd Mersenne prime. Since then, 10 new Mersenne primes have been found! What accounts for this progress?

Largely, it is distributed computing. The GIMPS project ("Great Internet Mersenne Prime Search") coordinates factorization efforts by thousands of computers worldwide. While there are millions of computers, few are actually doing anything useful at any given time. The genius of GIMPS is to harness these unused cycles to find new large primes.

I'm often asked, what is it good for? The answer is -- like a painting by da Vinci -- nothing, really. It adds to our knowledge about Mersenne primes, but it probably will never lead to a proof that infinitely many Mersenne primes exist. Nor does knowing large Mersenne primes contribute to cryptography. But -- again like the da Vinci painting -- the subtle mysteries of the primes have a worldwide and longstanding appeal.