Algebra Know-It-ALL

44 Natural Numbers and Integers

display—but it will be finite. Let’s call it y. What if we add 1 to y, getting a number even

larger than the product of all the primes? If you call that new number z, you can express it

like this:

z=y+ 1

= (2 × 3 × 5 × 7 × 11 × 13 × ... ×p)+ 1

Now we know that z has to be larger than p, because z is 1 more than, say, 2 ×p or 3 ×p

or 5 ×p or 7 ×p. But there’s something else interesting about z. If we divide z by any prime

number, we always get a remainder of 1. That’s because if we divide y by any prime, there’s no

remainder, and z is exactly 1 more than y.

We know that z can’t be prime, because we’ve already determined that z is bigger than p,

and we have already assumed that p is the largest prime. So z is composite. Because z is

composite, it must be divisible without a remainder by at least one prime, that is, one

element of set P. But wait! We just figured out a minute ago that if we divide z by any

element of P, we get a remainder of 1. Therefore, z can’t be composite. But it can’t be

prime either. But every natural number larger than 1 is either prime or composite! But ...

but ... but ... we are trapped!

There’s only one way out of this situation. Our original assumption, that there is a largest

prime number, must be false. Reductio ad absurdum, which we first encountered in the solu-

tion to Prob. 5 at the end of Chap. 2, comes to the rescue again!

How many primes?

The discovery that there is no largest prime number leads us straightaway into another impor-

tant truth: there are infinitely many prime numbers. When a mathematician proves a major

theorem like the one we just explored, and then some other fact follows on its heels, that

secondary fact is called a corollary.

Let’s start out by assuming that the number of primes is finite, and load up our reductio ad

absurdum “cannon” for another shot. This time it’s going to be easy. If the number of primes

is finite, we can list them all. That means one of them has to be larger than all the others, so it

is the largest prime. But we just discovered that there is no largest prime. Contradiction! The

number of primes can’t be finite, so it must be infinite.

Are you confused?

When you have found the prime factors for a composite number, you can write the product out in any

order. But unlike a listing of the elements of a set, in which you are allowed to list any element only once,

you must be sure to include all the occurrences of a prime factor if it appears more than once. Take this

example:

6,615= 3 × 3 × 3 × 5 × 7 × 7

You will get into trouble if you say, “The set of prime factors of 6,615 is {3, 5, 7}.” How do you know

whether a given factor occurs once, twice, three times, or more?

Some people get around this issue by putting a little superscript called an exponent after a number in the

set to indicate that it occurs more than once as a factor. They write that the set of prime factors of 6,615 is