Number Theory 21

in the second case, since there are now fewer than k factors in the product, we conclude

by our assumption on k that p must divide one of the n

i

for 2 ≤ i ≤ k. So in any case, p

divides some n

i

, and the lemma is proved.

3.4 Fundamental theorem of arithmetic, uniqueness

Finally, we can prove the uniqueness part of the fundamental theorem of arithmetic.

Theorem 15 (Fundamental theorem, uniqueness). Every positive integer has at most

one prime factorization, in the sense that any two factorizations are simply rearranging

the order of the prime factors appearing in them.

Proof. We have already proved the existence claim in theorem 10. What remains is the

uniqueness claim. Suppose that all the numbers smaller than a number n have at most

one representation as a product of primes (unique up to rearranging the order in which

the prime factors appear in the product). Suppose that n = p

1

···p

k

= q

1

···q

r

are two

representations of n as a product of primes. Since p

1

divides n, it follows by lemma 14 that

p

1

must divide one of the q

j

, and since these are all prime, it must be equal to one of the q

j

.

It might as well be q

1

, by rearranging the qs. But in this case, we have p

2

···p

k

= q

2

···q

r

,

since these are both n/p

1

, and by our assumption on n, these two products are a simple

rearrangement of each other. So the original products also are obtained by rearranging,

and we are done.

The fundamental theorem of arithmetic (theorem 9) amounts to the combination of the

existence claim of theorem 10 and the uniqueness claim of theorem 15, so it is now proved.

3.5 Infinitely many primes

Let us turn now to another classical result, the fact that there are infinitely many primes.

This is a classic argument, often attributed to Euclid, known for thousands of years.

Theorem 16. There are infinitely many prime numbers.

Proof. Suppose that you have a list of finitely many prime numbers:

p

1

, p

2

, ..., p

n

.

Let N = (p

1

p

2

···p

n

) + 1, the result of multiplying them together and adding 1. Observe

that if you should divide N by any particular prime number p

i

on your list, then there will

be a remainder of 1. In particular, this number N is not divisible by any prime number on

your list. But N is a product of primes, as every natural number is, and so there must be a

prime that is not on the list. Thus, no finite list of numbers includes all the primes, and so

there must be infinitely many of them.