18 Chapter 3

One sometimes hears that 5

n

means that we multiply 5 by itself n times. This is not really

accurate, however, if what is meant is that we have n multiplications, since 5

2

means 5 ×5,

which is only one act of multiplication; we would be more correct, therefore, to say that n

refers to the number of factors, rather than to the number of times we are multiplying. This

is a fence-post error, discussed further in chapter 5. So we regard 5

1

as a product consisting

of just one factor. Similarly, we take 5

0

= 1 as a product with no factors at all, the empty

product. This is the sense in which 1 is a “product” of prime numbers.

The thing to notice here is that, even if we had stated the theorem as, “Every positive in-

teger is either prime or a product of primes,” it still would not be correct without this empty

product convention, since the number 1 is a positive integer, but it cannot be expressed as

a product of primes except as the empty product. Without the empty and singleton product

considerations, therefore, we would have to say, “Every integer greater than 1 is either

prime or a product of primes.” But is it not both simpler and more elegant to state the the-

orem as we have in theorem 9? We have included the primes themselves each as a product

with only one factor and the number 1 as the empty product.

So let us now prove the fundamental theorem, which makes two essentially different

claims: an existence claim and a uniqueness claim. Namely, the existence claim is that

every positive integer admits at least one prime factorization, and the uniqueness claim

is that every number admits at most one prime factorization, in the sense that any two

factorizations of the same number are rearrangements of one another. Let us begin with

the existence claim, since this is perhaps more familiar, as well as easier to prove.

Theorem 10 (Fundamental theorem, existence). Every positive integer can be expressed

as a product of prime numbers.

Proof. Let us prove that every positive integer has the property. The number 1 is expressed

as the empty product, and so we have made a start. Suppose that all the numbers up to

some number n have the property, where n > 1, and now consider whether n itself has

the property. If n happens to be prime, then indeed, it is expressible as a product of just

one prime factor, itself, and so it would have the property. Otherwise, n is not prime, and

so we may factor it as n = ab for some numbers a and b, both smaller than n. Because

we assumed that the property holds up to n, we know that both a and b are expressible as

products of primes. So a = p

1

···p

k

and b = q

1

···q

r

for primes p

i

and q

j

, where 1 ≤ i ≤ k

and 1 ≤ j ≤ r. By simply combining these products, we can now realize n also as a product

of primes:

n = ab = p

1

···p

k

· q

1

···q

r

.

So the property does indeed hold at n. We have therefore proved that whenever the property

holds up to a number n, then it holds at the number n. In other words, there can be no

minimal counterexample to the property; thus, there can be no counterexample at all. So

every number has the property.