Prime numbers have always fascinated mathematicians. They pepper the natural numbers with a disconcerting degree of unpredictability, yet are distributed quite evenly. So much of mathematics finds surprising and beautiful connections between seemingly disparate concepts. There is a reassuring recurrence of patterns. This is not so with the primes.
Number enthusiasts have long sought underlying rules to explain why certain numbers are prime. Two different approaches go hand in hand — proving that a given number is prime, and predicting patterns to find undiscovered primes.
The Sieve of Eratosthenes exemplifies an early attempt. Picture the natural numbers (any number you can use to count objects) ordered on a line. The first number is one. Recalling the definition of a prime number (a natural number greater than one with no factors besides itself and one), we see that one itself is off the table. Beginning with two, we’ve already found our first prime! Indeed, it meets all of the specifications. We also now know a lot of numbers that aren’t prime — that is, all multiples of two.
With hardly any work at all, we can cross out half of the numbers we were considering. The next number that isn’t crossed out is three — another prime! After crossing out every third number, the next unmarked number is five, again prime. If you haven’t caught the pattern, as you work your way along the number line, any unmarked number you come across will be prime, because if it had any factors, you would have crossed it out along with them already.
The Sieve of Erastothenes is a fairly efficient algorithm to find all the primes in the range of the low hundreds, but it’s easy to see that without the aid of a computer it is impractical for anything larger. It also can’t just tell you if any given number is prime without running through the whole process.
Exploiting modular arithmetic, Fermat’s Little (but not his last) Theorem can be used to prove that a given number is composite (not prime) or likely to be prime. Unfortunately, some composite numbers can pass this and other primality tests. These numbers are called psuedoprime.
Some mathematicians noticed that (2^n)-1 tends to be prime when n is prime. Initially, it was thought this worked for all primes. Hudalricus Regius busted that myth in 1536 when he found that (2^11)-1 = 2047 = 23*89. Marin Mersenne, a french monk, postulated in 1644 that it was true for n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, and that for n < 257, all the rest result in composites. He wasn’t completely right (the complete list is n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127), but he still got his name on primes of the form (2^n)-1.
With the advent of high-performance electronic computing in the second half of the twentieth century, researchers began using computers to find increasingly large primes. It is no accident that the largest primes discovered are all Mersenne primes. This is because they are the easiest large numbers to prove prime.
The GIMPS (Great Internet Mersenne Prime Search) is a distributed computing project that has been working to find new primes since 1996. In its 17 years, GIMPS has found all 14 of the largest mersenne primes. According to mersenne.org, the system can handle up to 150 trillion calculations per second on 360,000 CPUs. Volunteers can contribute to the project by installing the GIMPS software on their personal computers. GIMPS offers cash rewards of $3,000 to the lucky finders of new primes. In addition, the Electronic Frontier Foundation is offering a $150,000 bounty for the first prime with at least 100 million digits and $250,000 for at least one billion digits.
Dr. Curtis Cooper, of the University of Central Missouri, recently found his third record-breaking prime. On January 25, Curtis confirmed that (2^57,885,161)-1 was the 48th mersenne prime. It has 17,425,170 digits. The proof took 39 days to compute. He is eligible for a $3,000 award from GIMPS.
