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 n_{1}. If
n_{1} is even, write it as 2 x n_{2}, and
hence n as 2 x 2 x n_{2}. 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 5^{1/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.