V.14 The Fundamental Theorem of Arithmetic
The fundamental theorem of arithmetic is the assertion that every positive integer can be expressed in exactly one way as a product of prime numbers. These prime numbers are known as the prime factors of the original number and the product itself is the prime factorization. To give a few examples: 12 = 2 × 2 × 3, 343 = 7 × 7 × 7, 4559 = 47 × 97, and 7187 is itself a prime. This last number shows that the word “product” should be interpreted so as to include the case where there is only one prime involved. As for the phrase “exactly one way,” it is understood that the order in which the primes are multiplied is not significant, so, for example, the products 47 × 97 and 97 × 47 are not regarded as different.
The following inductive procedure allows one to find the prime factorization of a given positive integer n. If n is prime, then we have found it already. Otherwise, let p be the smallest prime factor of n and let m = n / p. Since m is smaller than n, we know by induction how to find the prime factorization of m, and this, together with p, gives it to us for n. In practice, what this means is that we generate a sequence of numbers, where each number in the sequence is the previous one divided by its smallest prime factor. For example, if we start with the number 168, then the sequence begins 168, 84, 42, 21. At this point we cannot divide by 2, but 3 is a factor of 21 so the next number in the sequence is 7. Since 7 is a prime, the process stops. Looking back, we find that we have shown that 168 = 2 × 2 × 2 × 3 × 7.
Once one is used to this method, it comes to seem inconceivable that a number could have two genuinely different prime factorizations. But the method does not guarantee this at all. Suppose we successively divide by the largest prime factor rather than the smallest. Why should this not give a completely different set of primes? It is hard to think of an argument that does not use a phrase such as “the prime factorization of n,” thereby implicitly assuming what it sets out to prove.
It is possible to show in a rather precise way that the fundamental theorem of arithmetic is not obvious, by looking at an algebraic structure where the notion of prime factorization makes sense but numbers can have more than one prime factorization. This structure, denoted 
(
), is the set of all numbers of the form a + b, where a and b are integers. Such numbers can be added and multiplied just like ordinary integers. For example,
and
In this structure, we can regard a number x = a + bas prime if its only factors are ±1 and ±x. (This would also be a natural definition if we wanted to extend the notion of primes from the positive integers to all integers.) It can be shown quite easily that 2 and 3 are both primes (though it is not immediately obvious since there are now more possibilities for factors). Two other primes are 1+ and 1–. But we can write 6 either as 2 × 3 or as (1 + )(1 – ), so 6 has two different prime factorizations. For a further discussion of this point see ALGEBRAIC NUMBERS [IV.1 §§4-8].
What this example shows is that any proof of the fundamental theorem of arithmetic must use some feature of , the set of integers, that is lacking in (). Since addition and multiplication work in a very similar way in both structures, it is not very easy to find such a feature, or at least not one that is relevant. It turns out that the important property that () does not have is an appropriate analogue of the following basic principle for integers: that if m and n are integers, then one can write n = qm + r with 0 ≤ r < |m|. This fact underlies EUCLID’S ALGORITHM [III.22], which plays an important role in the most commonly given proof of unique factorization.