# VACETS Regular Technical Column

The VACETS Technical Column is contributed by various members , especially those of the VACETS Technical Affairs Committe. Articles are posted regulary on [email protected] forum. Please send questions, comments and suggestions to [email protected]

September 10, 1996

# Largest Known Prime Number Discovered

About 2 years ago, Andrew Wiles, a researcher at Princeton, claims to have proved the Fermat's Last Theorem (FLT) and later a large gap was found in the proof. (The gap was filled later at the end of 1994.) At that time, we, the VACETSERS, had debated on proving the FLT using numerical methods (i.e., using computer to crank out the solutions to the famous theorem). One of the first steps in numerical method is to find the prime numbers, and from that, a "fastest prime number generator" war was waged among us the VACETSERS. The result of that "war" was that we were able to reduce the time from tens of seconds to find all the primes below 1 million to less than 1 second to find all the primes below 10 million. It was an improvement of more than 100. It was a fun war. (Actually, for me, anything involved with numbers, especially prime numbers, is fun.)

Shortly after that "fastest prime number generator" war, Thomas R. Nicely, Professor of Mathematics at Lynchburg College, Virginia, computed the sums of the reciprocals of the twin primes (such as 11 and 13), triplets (such as 11, 13, and 17), and quadruplets (such as 11, 13, 17, and 19) up to a very large upper bound (about 10 trillion). He discovered during the summer and fall of 1994 that one of the reciprocals had been calculated incorrectly by a Pentium computer, although a 486 system gave the correct answer; this led to the publicization of the hardware divide flaw in the Pentium floating point unit.

Last week, 9/3/96, an other prime number news surfaced: The largest known prime is found by a SGI/Cray supercomputer in the process of quality assurance testing on its systems. The new prime number, 2^1257787-1 (which denotes 2 multiplied by itself 1,257,787 times minus one) is the 34th Mersenne prime, discovered by David Slowinski and Paul Gage. It took about 6 hours on a Cray T94 supercomputer to check this number. For a 90-MHz Pentium, it would take about 60 hours. The previous largest known Mersenne prime, 2^859433-1, was also discovered by Slowinski and Gage in 1994.

Before getting too far with the new discovery, let's review some basic of prime numbers.

What is a prime number? A prime number is a positive integer that can be divided only by itself and the number 1. The first few prime numbers are 2, 3, 5, 7, 11...

What is a Mersenne prime? A Mersenne prime is a prime number that has the form 2^p-1 where p is also a prime. Ex: 3=2^2-1 and 7=2^3-1 are the first 2 Mersenne primes.

History: Many early mathematicians felt that the numbers of the form 2^p-1 were prime for all primes p. But, in 1536, Hudalricus Regius showed that 2^11-1 = 2047 was not prime (it is 23*89). This meant that 2^p-1 might or maight not be prime. By 1588 Pietro Cataldi had correctly verified that 2^17-1 and 2^19-1 were both prime.

In 1644, Father Marin Mersenne, a French monk, stated that the numbers 2^p-1 were prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257. Mersenne's conjecture, even though later proved to be incorrect, got his name attached to these numbers.

It was obvious to Mersenne's peers that he could not have tested all of these numbers, but they could not test them either.

Cataldi's prime (p=19) stood to be the largest known prime for about 2 centuries until Leonhard Euler in 1772 proved that 2^31-1 is prime. (Through out the history, Mersenne primes were almost always the largest known primes.) This established the record for another century until 1876, when Edouard Lucas showed that 2^127-1 (which is a 39 digit number) is prime, and that took the record as far as the age of the electronic computer. Seven years later I.M. Pervushin showed 2^61-1 was prime, so Mersenne had missed this one. In the early 1900's R.E. Powers showed that Mersenne had also missed the primes 2^89-1 and 2^107-1. Finally, by 1947, Mersenne's range, p < 258, had been completely checked and it was determined that the correct list is: p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127.

In 1952 the Mersenne numbers p = 521, 607, 1279, 2203, and 2281 were proved to be prime by Robinson using an early computer and the electronic age had begun.

By 1996 a total of 34 Mersenne primes have been found. The largest and most recent is p = 1,257,787 which has 378,632 decimal digits.

The table of known Mersenne primes as of September 3, 1996 is shown below.

```   n         p    Year    Discoverer
--    ------    ----    ----------------------
1         2      -     -
2         3      -     -
3         5      -     -
4         7      -     -
5        13    1461    Anonymous
6        17    1588    P. A. Cataldi
7        19    1588    P. A. Cataldi
8        31    1750    L. Euler
9        61    1883    I. M. Pervushin
10        89    1911    R. E. Powers
11       107    1914    R. E. Powers
12       127    1876    E. Lucas
13       521    1952    R. M. Robinson
14       607    1952    R. M. Robinson
15      1279    1952    R. M. Robinson
16      2203    1952    R. M. Robinson
17      2281    1952    R. M. Robinson
18      3217    1957    H. Riesel
19      4253    1961    A. Hurwitz & J. L. Selfridge
20      4423    1961    A. Hurwitz & J. L. Selfridge
21      9689    1963    D. B. Gillies
22      9941    1963    D. B. Gillies
23     11213    1963    D. B. Gillies
24     19937    1971    B. Tuckerman
25     21701    1978    L. C. Noll & L. Nickel
26     23209    1979    L. C. Noll
27     44497    1979    D. Slowinski & H. Nelson
28     86243    1982    D. Slowinski
29    110503    1988    W. N. Colquitt & L. Welsch, Jr.
30    132049    1983    D. Slowinski
31    216091    1985    D. Slowinski
32?   756839    1992    D. Slowinski & P. Gage
33?   859433    1994    D. Slowinski & P. Gage
34?  1257787    1996    D. Slowinski & P. Gage
```

It is not known if these last three primes are the 32nd through 34th Mersenne primes as the region between them and the previous primes has not been completely tested. Notice that the 29th Mersenne was found while scanning the region between two primes found five years earlier.

The way to determine if 2^p - 1 is prime, given that p is prime, is to use the Lucas-Lehmer test:

u := 4; for i := 3 to p do u := (u^2 - 2) mod (2^p - 1); if u == 0 then 2^p - 1 is prime; else 2^p - 1 is composite;

The theory for this test was initiated by Lucas in the late 1870's and then made into this simple test about 1930 by Lehmer.

Note that, with the discovery of the new prime number, a new perfect number can also be generated. A perfect number is equal to the sum of its factors. For example, 6 is perfect because its factors 1, 2 and 3, when added together, equal 6; the next is 28 = 1+2+4+7+14. Mathematicians don't know how many perfect numbers exist. They do know, however, that all even perfect numbers have a direct relationship to Mersenne primes, P = 2^(p-1)*(2^p-1) where 2^p-1 is a Mersenne prime. The new Mersenne prime has 378,632 digits and the new even perfect number generated with the new Mersenne prime is the 34th known perfect number and has 757,263 digits. It is not known whether or not there is an odd perfect number, but if there is one then it is a perfect square times an odd power of a single prime; it is divisible by at least eight primes and has at least 29 prime factors; and it has at least 300 decimal digits.

Finding the largest prime numbers does not have to be exclusive right of high-powered supercomputers. A Florida-based programmer has organized a hunt for the search for Mersenne Primes using PC. George Woltman, the search organizer, wanted to take advantage of the fact that PC central processors waste most of their computing power because they run on idle much of the time. So Woltman wrote a program that uses PC, when it's not doing anything else, to help find Mersenne primes. Then he spread the word on the Internet, in part by setting up a special World Wide Web site, and asked for help. About 400 volunteers from around the world have signed up, and Woltman is looking for more. If you'd like to help, you can check out the web at

https://ourworld.compuserve.com/homepages/justforfun/prime.htm.

Below is the list of some of the web sites containing the related information on the latest Mersenne prime number.

HAPPY NUMBER CRUNCHING, EVERYONE.

Vo Ta Duc

[email protected]

For discussion on this column, join [email protected]