Page 282 - Discrete Mathematics and Its Applications

4.3 Primes and Greatest Common Divisors 261

Q − p 1 p 2 ··· p n = 1. Hence, there is a prime not in the list p 1 ,p 2 ,...,p n . This prime is
either Q, if it is prime, or a prime factor of Q. This is a contradiction because we assumed that
we have listed all the primes. Consequently, there are infinitely many primes.

Remark: Note that in this proof we do not state that Q is prime! Furthermore, in this proof, we
have given a nonconstructive existence proof that given any n primes, there is a prime not in
this list. For this proof to be constructive, we would have had to explicitly give a prime not in
our original list of n primes.

Because there are infinitely many primes, given any positive integer there are primes greater
than this integer. There is an ongoing quest to discover larger and larger prime numbers; for
almost all the last 300 years, the largest prime known has been an integer of the special form
n
p
2 − 1, where p is also prime. (Note that 2 − 1 cannot be prime when n is not prime; see
Exercise 9.) Such primes are called Mersenne primes, after the French monk Marin Mersenne,
who studied them in the seventeenth century.The reason that the largest known prime has usually
been a Mersenne prime is that there is an extremely efficient test, known as the Lucas–Lehmer
p
test, for determining whether 2 − 1 is prime. Furthermore, it is not currently possible to test
numbers not of this or certain other special forms anywhere near as quickly to determine whether
they are prime.
2
7
3
5
EXAMPLE 5 The numbers 2 − 1 = 3, 2 − 1 = 7, 2 − 1 = 31 and 2 − 1 = 127 are Mersenne primes,
while 2 11 − 1 = 2047 is not a Mersenne prime because 2047 = 23 · 89. ▲
Progress in finding Mersenne primes has been steady since computers were invented. As of
early 2011, 47 Mersenne primes were known, with 16 found since 1990. The largest Mersenne
prime known (again as of early 2011) is 2 43,112,609 − 1, a number with nearly 13 million decimal
digits, which was shown to be prime in 2008. A communal effort, the Great Internet Mersenne
Prime Search (GIMPS), is devoted to the search for new Mersenne primes. You can join this
search, and if you are lucky, find a new Mersenne prime and possibly even win a cash prize. By
the way, even the search for Mersenne primes has practical implications. One quality control test
for supercomputers has been to replicate the Lucas–Lehmer test that establishes the primality of
a large Mersenne prime. (See [Ro10] for more information about the quest for finding Mersenne
primes.)

THE DISTRIBUTION OF PRIMES Theorem 3 tells us that there are infinitely many primes.
However, how many primes are less than a positive number x? This question interested mathe-
maticians for many years; in the late eighteenth century, mathematicians produced large tables

MARIN MERSENNE (1588–1648) Mersenne was born in Maine, France, into a family of laborers and
attended the College of Mans and the Jesuit College at La Flèche. He continued his education at the Sor-
bonne, studying theology from 1609 to 1611. He joined the religious order of the Minims in 1611, a group
whose name comes from the word minimi (the members of this group were extremely humble; they consid-
ered themselves the least of all religious orders). Besides prayer, the members of this group devoted their
energy to scholarship and study. In 1612 he became a priest at the Place Royale in Paris; between 1614 and
1618 he taught philosophy at the Minim Convent at Nevers. He returned to Paris in 1619, where his cell
in the Minims de l’Annociade became a place for meetings of French scientists, philosophers, and mathe-
maticians, including Fermat and Pascal. Mersenne corresponded extensively with scholars throughout Europe,
serving as a clearinghouse for mathematical and scientific knowledge, a function later served by mathematical journals (and today
also by the Internet). Mersenne wrote books covering mechanics, mathematical physics, mathematics, music, and acoustics. He
studied prime numbers and tried unsuccessfully to construct a formula representing all primes. In 1644 Mersenne claimed that
p
2 − 1 is prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 but is composite for all other primes less than 257. It took over 300
p
years to determine that Mersenne’s claim was wrong five times. Specifically, 2 − 1 is not prime for p = 67 and p = 257 but is
prime for p = 61, p = 87, and p = 107. It is also noteworthy that Mersenne defended two of the most famous men of his time,
Descartes and Galileo, from religious critics. He also helped expose alchemists and astrologers as frauds.