Numbers: Their Tales, Types, and Treasures.

Chapter 8: Special Numbers

8.1.PRIME NUMBERS

We begin by reviewing the definition of a prime number—a number greater than 1 that has only two divisors: the number itself and the number 1. For example, the first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, and 19. We can notice that there is only one even prime number, 2, and all the other prime numbers are odd. In chapter 4 we characterized prime numbers as nonrectangular numbers greater than 1. It is impossible to represent a prime number by a rectangular array of objects with more than one row or column (see figure 8.1).

Figure 8.1: The number 11 is a prime number.

A rectangular number, on the other hand, can be arranged in rectangular form, which means that it can be written as a product of at least two numbers greater than 1, such as 45 = 3 × 15 = 9 × 5 = 3 × 3 × 5. Such numbers are also called composite numbers.

In fact, every composite number can be written as a product of prime numbers. For example, 297 = 3 × 3 × 3 × 11, and 9,282 = 2 × 3 × 7 × 13 × 17. It is important to note that the prime numbers that occur in the factorization of a composite number are uniquely determined.

Every natural number greater than 1 either is a prime number itself or has exactly one factorization into primes.

This famous theorem was already known to Euclid. Because of its importance, it is called the fundamental theorem of arithmetic.

An early method for finding prime numbers was developed by the Greek scholar Eratosthenes (276–194 BCE). Using his method, we can list all the numbers—at least as many as we wish—beginning with the number 2, and cancel every successive multiple of 2. This leaves us with all the odd numbers. We then continue along with the next uncanceled number, in this case the number 3, and once again we cancel out all the successive multiples of 3. The next uncanceled number is the number 5, and once again all successive multiples of 5 become canceled. What remains uncanceled as we continue this process are all the prime numbers. Figure 8.2 shows this “sieve of Eratosthenes,” a table of the odd numbers, with straight lines striking out the multiples of 3, 5, 7, 11, and 13. The remaining encircled numbers are the prime numbers between 3 and 309. A listing of all prime numbers less than 10,000 is in the appendix, section 2.

Figure 8.2: Sieve of Eratosthenes.

Does the sequence of prime numbers continue indefinitely? Or will the process of canceling multiples eventually stop, when all numbers have been struck out? Euclid gave an ingenious proof that there are, indeed, infinitely many prime numbers. The argument is as follows: Suppose we know only a finite number of prime numbers—say, for example, 2, 3, 5, 7, 11, 13, 17, and 19. Then we can show that there must be another one. That one would be found by forming the product of all known prime numbers, and adding 1 to obtain a larger number, which for our example would be as follows:

2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 + 1 = 9,699,691.

This number is not necessarily a prime number—as is the case here, where 347 × 72,953 = 9,699,691. If this number were a prime number, then we would have found another prime. The product of successive known primes plus 1 may be a prime (e.g., 2 × 3 + 1 = 7) or may not be a prime (e.g., 3 × 5 + 1 = 16). Now assume that we did not generate a new prime—as was the case above. Then we will look for the smallest number q > 1 that divides this number exactly. The number q cannot be in our list of known prime numbers, because none of these divides 9,699,691 exactly (as there will always be a remainder 1). Then q must be a prime number itself, because otherwise, q would be a product of smaller numbers, which are also factors of 9,699,691, and then q would not be the smallest factor. So we have found a new prime number q that is not in our list of known prime numbers. For every finite list of prime numbers, we can find a new one using this procedure. Therefore, the list of all prime numbers cannot be finite.