AMERICAN MATHEMATICAL SOCIETY

Volume 21, Number 2, October 1989

*The book of prime number records*, by Paulo Ribenboim. Springer–Verlag, New York, Berlin, Heidelberg, 1988. xxiii + 476 pp., $49.80.

Do people ever ask you, "What is the largest known prime?" or "For how many zeros of the zeta function is the Riemann Hypothesis known to hold?" Now at last there is a book which answers many questions of this type.

Guinness published the *Book of World Records* to settle arguments. Ribenboim has written a similar book to settle arguments about prime numbers. The world would be very civilized indeed if a brawl in a pub began with a dispute about how many twin primes are known. Some of the records which are reported are the results of computer searches and some of them are statements of theorems which approach best possible results.

Euclid's proof that there are infinitely many primes is well known to most mathematicians: If there were only finitely many primes, list all of them, multiply them together and add 1. The resulting number is not divisible by any prime on the list. However, either it is prime or it has a prime factor not on the list. In either case, there exists a prime not on the list which was supposed to contain all primes.

Some students misunderstand this proof and believe that it says that if you multiply together all the primes up to some point, and add 1, the result must be prime. Write *p#* for the product of all primes *p*.*p#* + 1*p* = 2,*p#* + 1*p* = 31,*p* for which *p#* + 1*p* = 13649.

Write π(*x*) for the number of primes up to *x*. A simple approximation for *x*)*x*) ≈ *x*/ln *x*.*x*) ≈ Li(*x*).*x* for which *x*)^{16}) =*second* fastest. (The overhead of the algorithm which is ultimately fastest makes it slower than the second best one for numbers which are small enough to perform the calculation at all.)

The distribution of prime numbers is closely connected to the location of the zeros of the Riemann zeta function. This function of a complex variable has infinitely many zeros with real pan between 0 and 1. If all of these zeros had real pan equal to 1/2, as Riemann conjectured in his famous Riemann Hypothesis, then Li(*x*) would be a very good approximation to *x*)*x*) =*x*) + *O*(√*x* ln *x*).*s*) = 1/2.

What is the longest table of prime numbers ever made? The longest table ever published is that of D. N. Lehmer [7], which lists the primes up to 10 017 000. In the middle of the nineteenth century, Kulik prepared a table of factors of all numbers (other than multiples of 2, 3, and 5) up to 100 330 200. The primes up to this limit can be found easily in this table. However, there is only one copy of it (in the Vienna Academy of Sciences), one volume (out of 8) is missing, and the table contains too many errors to be worth publishing. In 1959, Baker and Gruenberger published a microcard table of the first six million primes – those up to 104 395 289. Now that we have computers, no more extensive tables are likely to be published because it is quite easy to generate a table of primes in a computer memory by the Sieve of Eratosthenes. Then the computer can perform the desired examination of the table and print a summary of the result. What then is the largest *x* so that all primes up to *x* have ever been formed and studied in a computer memory? Young and Potler [10] have computed all primes up to ^{13}

It is easy to exhibit large gaps between consecutive primes: A block of *N* consecutive composite numbers begins with *N* + 1)! + 2.*first *occurrence of a block of that length. The prime gaps have been tabulated by Young and Potler for primes up to ^{13}.

While Euclid knew that there are infinitely many primes, even today we do not know whether there are infinitely many pairs *p*, *p* + 2*x* for which we know exactly how many twin primes there are below *x* is 10^{11}: In 1976 Brent counted 224 376 048 primes *p* ≤ 10^{11}*p* + 2*x* is asymptotically *cx*/ln^{2 }*x*,*c* is an explicitly given constant.

About a dozen pairs of twin primes are known in which the numbers have more than 1000 digits. Most of these were discovered by Dubner, Keller and Atkin and Rickert. The three largest known pairs are ^{7650} ± 1,^{7701} ± 1^{11235} ± 1.

It is not trivial to prove that a number with more than 1000 digits is prime. The special form *k*2^{n} ± 1*N* is a large prime, then it is almost always easy to prove that *N* is prime provided that one knows the prime factorization of either *N* – 1*N* + 1.

**Theorem 1 (Proth, Pockington, Lehmer, Selfridge)**. If *N* is odd and if for each prime *q* dividing *N* – 1*a* for which *a*^{N–1} ≡ 1(mod *N*),*a*^{(N–1)/q} ≠ 1(mod *N*),*N* is prime.

The *a*'s are found by trial and error. Usually it is easy to find them among the small quadratic nonresidues of *N*. There is a similar theorem for the case of *N* + 1*M _{p}* = 2

**Theorem 2 (Lucas, Lehmer)**. If *p* is odd, then *M _{p}* is prime if and only

The three largest known Mersenne primes are *M _{p}* for

The even perfect numbers are ^{p–1}*M _{p}*

The iterated use of Theorem 1 is an efficient method for generating large random primes for use in cryptography. To construct a secret *N*_{1} which you know is prime. (It doesn't have to be secret.) Try various random *k*_{1} until some *N*_{2} = 2*k*_{1}*N*_{1} + 1^{N2–1} ≡ 1(mod *N*_{2}).*N*_{2} is probably prime.) Try to prove that *N*_{2} is prime via Theorem 1. (If you fail, try more values of *k*_{1}.) Now repeat the process with 1 added to the subscripts. After nine iterations you arrive at a *N*_{10} which no one has ever seen before.

There are two ways that primes may be in arithmetic progressions: They may lie in a given (infinite) arithmetic progression or they may form the entire (finite) progression. Dirichlet proved that if the first term *a* and common difference *d* > 1*a* and *d* > 1*p*(*d*, *a*)*a* + *kd*;*k* > 0}.*p*(*d*, *a*)*d*) ln *d**d*)*d* with *a* < *d*.*d* > 1*p*(*d*, *a*) < φ(*d*) ln^{1+ε }*d**a* relatively prime to *d* with *a* < *d*.*a* to lie between 1 and *d*. Define *p*(*d*) to be the greatest *p*(*d*, *a*)*a* < *d**a* relatively prime to *d*. Linnik's theorem asserts that there is a constant *L* > 1*p*(*d*) < *d ^{L}*

Even less is known about primes which form an arithmetic progression. In 1939, van der Corput proved that there are infinitely many three-term arithmetic progressions of primes. However, we still do not know whether there are infinitely many arithmetic progressions consisting of four primes. Computer searches have uncovered many arithmetic progressions consisting of a small number of primes. The record is a progression of 19 primes discovered by Pritchard in 1985. The first term is 8 297 644 387 and the common difference is 4 180 566 390.

Some large primes are interesting because they divide numbers of simple form such as *b ^{n}* ± 1,

Ribenboim's book is informative and easy to read. One can begin reading almost anywhere. The book is accessible to nonexperts. It is not just a list of records. Much background material is included, too. Many simple proofs are given. It is an excellent source of ideas for a lecture to a mathematics club or high school.

1. | R. P. Brent and G. L. Cohen, |

2. | J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman and S. S. Wagstaff, Jr., ^{n}b = 2,up to high powers, Contemporary Math., vol.22, Amer. Math. Soc., Providence, R.I., 1983, second edition 1988. |

3. | J. R. Chen, 22 (1979), pp. 859–889. |

4. | H. Dubner, |

5. | P. D. T. A. Elliott and H. Halberstam, |

6. | J. C. Lagarias, V. S. Miller and A. M. Odlyzko, |

7. | D. N. Lehmer, |

8. | D. Shanks, |

9. | J. van de Lune. H. J. J. te Riele and D. T. Winter. |

10. | J. Young and A. Potler, |

S. S. Wagstaff, Jr.

Purdue University