The Art and Craft of Problem Solving

7.1 PRIMES AND DIVISIBILITY 223

There are infinitely many primes.

This was Problem 2.3.2 1 on page 51, but in case you did not solve it, here is the
complete proof, a classic argument by contradiction known to the ancient Greeks and
written down by Euclid. This proof is one of the gems of mathematics. Master it.

We start by assuming that there are only finitely many primes PI, P 2 , P 3 , ... ,PN.

Now (the ingenious crux move!) consider the number Q:= (PIP 2 P 3 '" PN) + 1. Either

it is prime, or it is composite. The first case would contradict the hypothesis that PN

is the largest prime, for certainly Q is much greater than PN. But the second case also

generates a contradiction, for if Q is composite, it must have at least one prime divisor,

which we will call p. Observe that P cannot equal PI, P 2 ,"" PN, for if you divide Q

by any of the Pi, the remainder is 1. Consequently, P is a new prime that was not in

the list PI, P 2 , ... ,PN, contradicting the hypothesis that this was the complete list of

all primes. _

7.1.1 There is a tiny gap in our proof above. We made the blithe statement that Q had
to have at least one prime factor. Why is this true? More generally, prove that every
natural number greater than 1 can be factored completely into primes. For example,

360 = 2^3. 32 · (^5). Suggestion: use strong induction, if you want to be formal.
In fact, this factorization is unique, up to the order in which we write the primes.
This property of unique factorization is called the Fundamental Theorem of Arith­

metic (FTA).I We call the grouping of factors into primes the prime-power factor­

ization (PPF). An ugly, but necessary, notation is sometimes to write a number n in

"generic" PPF:

n --peI^1 pe2 2 ... pet t·

You probably are thinking, "What is there to prove about the FTA? It's obvious."

In that case, you probably also consider the following "obvious:"

Let x, y be integers satisfying 5x = 3y. Then 31 x and 5 1 y.

But how do you prove this rigorously? You reason that 5x is a multiple of 3 and

since 3 and 5 are different primes, x has to contain the 3 in its PPF. This reasoning

depended on the FTA, for if we did not have unique factorization, then it might be

quite possible for a number to be factored in one way and have a 5 as one of its primes

with no 3, and factored another way and have a 3 as one of its primes, without a 5.

Example 7.1.2 Not convinced? Consider the set E := {O, ±2, ±4, ... } that contains

only the even integers.

• Notice that 2, 6, 10 , 30 are all "primes" in E since they cannot be factored in E.

• Observe also that

60 = 2. 30 = 6. 10 ;

I "PTA" is also used to abbreviate the Fundamental Theorem of Algebra.