# And the winning number is...

### By Chris Caldwell

#### GIMPS finds a Multi-million digit prime!

One way to win a lottery is for several thousand folks to group together
and buy tens of thousands of tickets, then there is a fair chance that one
of the group will win. One June first, 1999, this strategy paid off for
GIMPS: the **G**reat **I**nternet
**M**ersenne **P**rime **S**earch. On that day Nayan Hajratwala found
a 2,098,960 digit Mersenne prime:

2^{6972593}-1.

This is GIMPS fourth Mersenne prime in as many years and the 38th known Mersenne prime (though it may not be the 38th in order of size since not all smaller exponents have been checked.)

So what has this to do with the lottery? Money for one thing. This makes Hajratwala eligible for the $50,000 award that is offered by the Electronic Frontier Foundation (EFF). This time Hajratwala will pocket the whole $50,000. Larger primes will earn up to $250,000!

#### What is a Mersenne prime?

A prime is any integer
greater than 1, which has only 1 and itself for positive divisors. (For example,
the prime factors of 10 are 2 and 5.) The first few primes are 2, 3, 5, 7 and 11. Mersenne primes are those
which are a power of two, minus one. For example, the first few are 2^{2}-1=3,
2^{3}-1=7, 2^{5}-1=31, 2^{7}-1=127. These first
few were known to the ancient Greeks several hundred years before Christ.
See our page on Mersenne Numbers for more information, history and links (and be sure to check out the link
between Mersennes and perfect
numbers!).

#### How was it found?

Just how did Nayan Hajratwala (a PricewaterhouseCoopers employee in Plymouth, Michigan) find this prime? Not by himself! The key players are George Woltman, Scott Kurowski, and the 12,600 members of GIMPS and PrimeNet.

GIMPS was started by George Woltman to provide free software to find Mersenne primes and a database to coordinate the efforts of those involved. Scott Kurowski's company, Entropia.com, provided the distributed computing technology and services to make it trivial for anyone to join in the search via PrimeNet.

"This has got to be the best email message I've ever read!" Nayan responded.Nayan's home computer, a 350 MHz IBM Aptiva, used 111 days of idle time to find this prime, though it could have been done in three weeks if run full time on the same computer. David Willmore first verified the new Mersenne prime using a program written by Ernst Mayer (this took two weeks on a 500 MHz Alpha workstation).

For more information on PrimeNet and GIMPS see the official press release.

#### How do you show a number this big is prime?

We can check small numbers for primality by just dividing by the lesser integers. But to do that with a number the size of this new prime would take far longer than the universe has been in existence. The key to winning a prize this size is a theorem developed by Lucas in the late 1870's and simplified by Lehmer, now called the Lucas-Lehmer Test. Even as simple as this test is, it could not be done quickly without using very clever programs to multiply the numbers. In 1968 Strassen discovered how to multiply quickly using Fast Fourier Transforms. He and Schönhage refined and published the method in 1971. GIMPS now uses an improved version of their algorithm developed by the long time Mersenne searcher Richard Crandall [see CF94].

**Nayan Hajratwala, George Woltman, and Scott Kurowski** share the
credit and glory for this prime with all of the others involved in this
effort! There are still infinitely many more giants left to
slay, so why not surf over to Woltman's GIMPS site and join the
search for the next record prime? Perhaps you too can earn thousands
of dollars with your computer's spare time!

#### Links to more information

For more information click on one of the following:- About
**this prime** - The official press release
- Woltman's announcement on the GIMPS mailing list
- Articles:
- San Jose Mercury News, 6 July 1999
- The Oregonian, 7 July 1999
- The complete decimal expansion
- text file (2 meg) alternate sites:
- New perfect number's complete expansion alternate sites:
- Curt Noll's site which has the expansion in decimal (in three forms) as well as the English name!
- How long is this number when typed?
- About
**the GIMPS and PrimeNet projects** - GIMPS Search Credits
- Internet PrimeNet Server
- Search Status via GIMPS or via PrimeNet
- About
**Mersenne primes** - Mersenne Primes definitions, theorems, lists...
- Marin Mersenne references, images, sounds...
- Mersenne Primes Bibliography
- Mersenne mailing list
- About
**primes in general**