One of the things one is taught at school is how to write a number as a product of primes: for example, 38 = 2 x 19, 192 = 2 x 2 x 2 x 2 x 2 x 2 x 3, 47 = 47 which is prime already, and so on. One quickly gets used to this process, and soon begins to take the following theorem for granted: every number can be written as a product of primes in essentially one way (where by `essentially' one means that e.g. 2 x 19 counts as the same factorization as 19 x 2). This theorem is known as the fundamental theorem of arithmetic.
Why does it seem intuitively obvious? Probably because one is taught an algorithm for finding the factorization and it is obvious that the algorithm works. Here it is: take your number n. If n is even, write n = 2 x n1. If n1 is even, write it as 2 x n2, and hence n as 2 x 2 x n2. Keep going like this until you reach an odd number. Now do the same process, but this time dividing by 3, and then 5, 7 etc. Eventually you will reach a number that is itself prime, and you have found the factorization of the original number n.
252 = 2 x 126 = 2 x 2 x 63 = 2 x 2 x 3 x 21 = 2 x 2 x 3 x 3 x 7
If you think it is obvious that the above algorithm works, then you are right - my sketchy description can easily be converted into a rigorous proof, but not of the fundamental theorem of arithmetic. All it shows is that every number can be factorized into primes, but it has nothing to say about the uniqueness. Why should there not be some other algorithm that also gives you a way of writing a number as a product of primes, but one which is not necessarily the same product of primes given by this algorithm?
The proof of the fundamental theorem of arithmetic is surprisingly complicated. In another page I have attempted to show that it is nevertheless natural. In this page, I want to show that there cannot be any very simple proof, and that this rather vague statement can be made precise.
The most important method of proving metamathematical facts is to devise appropriate models . Suppose for example that I am trying to prove a theorem about the integers. If I want a particularly simple proof, then I will try to use only a few properties of the integers in my argument. If, however, I can construct some other mathematical object (the model) with those properties for which the theorem is false, then it is clear that my proof cannot work. In order to prove the theorem I must use properties of the integers that distinguish them from the model where the theorem does not hold.
Here is a model which has many properties in common with the integers, but for which the fundamental theorem of arithmetic is false (because there are `numbers' that can be written as a product of primes in more than one way). It is the set W of all complex numbers of the form a+bx, where a and b are integers and x is the square root of -5. (For definiteness one could take x to be root 5 times i.) These can be added, subtracted and multiplied, and one always gets another number of the given form. Thus, in many ways, the set of these numbers behaves very like the set Z of integers. In fact, these numbers form an integral domain , which means, roughly speaking, that all the obvious axioms that are satisfied by addition and multiplication in Z - commutative, associative and distributive laws, the cancellation law ab=ac implies a=0 or b=c, existence of identity elements and additive inverses, but not multiplicative inverses - are true in W as well.
Why does unique factorization fail? Well, we must first decide what a prime is, which is not hard, except that a little care is needed over the analogue of the number 1. In a ring, an element e is called a unit if it has a multiplicative inverse. It is important not to count units as primes, since otherwise if ef=1, we can always put ef on the end of any factorization. This is the same reason that we normally do not count 1 as a prime even though it cannot be factorized into smaller numbers. Thus, a prime is a number which is not a unit and which cannot be written as a product of two non-units.
It is now simple to write down an example of an element of W with more than one factorization: 6. This equals 2 times 3, and it also equals (1+x)(1-x). (Recall that x was the square root of -5.) In order to be sure that this is a genuine example, we must of course check that 2, 3, 1+x and 1-x are all primes. A short argument is that any number of the form a+bx with b not equal to 0 has modulus at least 51/2, so two such numbers must multiply to something of modulus at least 5. Since all of 2, 3, 1+x and 1-x are smaller than this, the only way they can be factorized as (a+bx)(c+dx) is if either b or d is 0. It is now very easy to see in all four cases that this forces either a+bx or c+dx to be 1 or -1, and hence a unit.
What moral can be drawn from this example? It shows that any proof of the fundamental theorem of arithmetic must use more about the integers than the mere fact that they form an integral domain . In particular, it is not straightforwardly obvious from the definitions of addition, multiplication and prime factorization that prime factorizations are always unique. To put this another way, to prove the fundamental theorem of arithmetic one must identify some property of Z that distinguishes it from W, and this is a matter of some subtlety.
What, then, is the important difference between Z and W? It turns out to be that the Euclidean algorithm, which is at the heart of the usual proof of the fundamental theorem of arithmetic, works in Z. The basic lemma on which this algorithm depends is the following.
Let x and y be positive integers. Then it is possible to write x = qy + r for some pair of non-negative integers q and r with r < y.
Analogues of Euclid's algorithm work in other contexts, such as the ring of all polynomials with rational coefficients. There, given polynomials a and b, one can write a = qb + r, where q and r are polynomials and the degree of r is less than that of b. However, in any context in which the lemma applies there has to be some notion of smaller than to apply to the remainder. For the positive integers this is just the usual notion, and for polynomials it means `has smaller degree than'. The elements of W, on the other hand, do not come with a satisfactory ordering of this kind. A natural candidate for a notion of smallness would be `has smaller modulus than', but it turns out that the analogue of the lemma above is not true for this notion, or indeed for any other that would do the job.
Thus, many of the features of the usual proof of the fundamental theorem of arithmetic are unavoidable.