Uniqueness of factorization. Elementary number theory has for its object the study of the integers 0, ±1, ±2, …. Certain of these, the prime numbers, occupy a special position; they are the numbers m which are different from 0 and ±1, and which possess no factors other than ±1 and ±m. For example 2, 3, −5 are prime, whereas 6 and 9 are not, since 6 = 2·3, 9 = 32. The importance of the primes is due to the fact that, together with 0 and ±1, all the other integers can be constructed from them. The fundamental theorem of arithmetic asserts that every integer greater than 1 can be factored in one and only one way, apart from order, as the product of positive prime numbers. Thus

12 = 22·3 = 2·3·2 = 3·22

are the only factorizations of 12 into positive prime factors, and these factorizations all yield precisely the same factors; the only difference among them is in the order of appearance of the factors.

We shall give a proof of the fundamental theorem of arithmetic. In the course of it the following fact will play a decisive role: every collection, finite or infinite, of non-negative integers contains a smallest one. The validity of this assumption will not be debated here; it is certainly clear intuitively, and the reader may take it to be one of the defining properties of integers. Some preliminary theorems will be established first.