14

The Prime Numbers

The prime numbers have always enjoyed a special status among the integers. A prime number, or prime, for short, is an integer greater than 1 that can be divided only by itself and 1. The first 10 primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. The smallest—and the only even prime—is 2. The largest, as of this writing, is 2^57,885,161 − 1, a gargantuan 17,425,170-digit number that would fill some 2,500 pages if printed.¹ An integer greater than 1 that is not prime is called composite. The number 1 is considered neither prime nor composite.

The importance of the primes in number theory—and by extension, in much of mathematics—comes from the fact that every positive integer can be factored into primes in one and only one way. For example, 12 can be factored into 3 and 4, so 12 = 3 × 4. But 4 itself can be factored into 2 and 2, so we end up with 12 = 3 × 2 × 2. We could have started by factoring 12 into 2 and 6; but 6 = 2 × 3, so we get 12 = 2 × 2 × 3. Except for their order, we end up with the same set of primes. This fact, known as the fundamental theorem of arithmetic, is true for every positive integer greater than 1 (although for large numbers the factorization process may take a very long time and may even be impossible to achieve in practice). The primes are, therefore, considered the building blocks of all integers, playing a role somewhat analogous to that of the chemical elements in the periodic table. In fact, so fundamental are the primes to mathematics that it has been proposed to use them as a means of communication with extraterrestrial beings, if and when we find them.

Plate 14 shows a row of dots representing the number 17. As much as you may try, you cannot arrange these dots in a rectangular array: there will always be at least one left over. That, of course, is because 17 is prime—it is not the product of any smaller integers except itself and 1.

Primes of the form 2ⁿ − 1, like the prime 2^57,885,161 − 1 just mentioned, are known as Mersenne primes, after the Minimite friar and freelance mathematician Marin Mersenne (1588–1648). For 2ⁿ − 1 to be prime, n itself must be prime, but the converse is false: 2¹¹ − 1 = 2,047 = 23 × 89. The first five Mersenne primes are 2² − 1 = 3, 2³ − 1 = 7, 2⁵ − 1 = 31, 2⁷ − 1 = 127, and 2¹³ − 1 = 8,191. To date, only 48 Mersenne primes are known; the largest, discovered in 2013, is the number quoted earlier. It is not known how many Mersenne primes exist—or even if their number is finite or infinite.

In chapter 4 we mentioned that if 2ⁿ − 1 is prime, then 2ⁿ⁻¹ · (2ⁿ − 1) is perfect. Consequently, each newly discovered Mersenne prime automatically yields a new perfect number. Since the largest prime to date, 2^57,885,161 − 1, is the 48th known Mersenne prime, it follows that 2^57,885,160 · (2^57,885,161 − 1) is the 48th known perfect number.

Many questions about the primes are still unanswered, adding to the aura of mystery that has always surrounded these numbers. Two questions immediately come to mind: how many primes are there, and what is their law of distribution among the integers? The first question was answered by Euclid around 300 BCE. In a classic proof that became a model of simplicity, Euclid showed that there is no end to the primes: their number is infinite. Although the primes, on the average, thin out as we go to higher numbers, there is no last prime beyond which all integers are composite. We give Euclid’s proof in the appendix.

The second question—the distribution of primes among the integers—has intrigued mathematicians for centuries. In contrast to the elements of the periodic table, the primes do not seem to follow any recognizable pattern; in fact, all attempts to find a formula that would generate all primes have so far failed. We do know, however, something about their average distribution. In 1792, when he was just 15 years old, Carl Friedrich Gauss (1777–1855) examined a table of primes and announced that the number of primes below a given integer n increases approximately as n/ln n, where ln stands for natural logarithm (logarithm to the base e = 2.71828 …; we’ll come back to this number in chapter 33). Moreover, the approximation gets better with increasing n and approaches n/ln n as n → ∞. It was only in 1896, more than a hundred years after Gauss’s announcement, that Jacques Solomon Hadamard of France and Charles de la Valleé-Poussin of Belgium independently proved his conjecture. It is known as the prime number theorem.

In years past, the discovery of a new prime often made the news. In 1963, the University of Illinois issued a special cancellation stamp to commemorate their discovery of the largest prime then known: 2^11,213 − 1 (figure 14.1). This 3,376-digit number—the twenty-third Mersenne prime—was huge at the time of its discovery but is dwarfed by the primes that have been discovered since. But rest assured, still larger primes are lurking just around the corner, waiting to be discovered by today’s powerful supercomputers—or even home computers.

NOTE:

1. Source: The Largest Known Primes—A Summary, on the Web at http://primes.utm.edu/largest.html, 2013.