Here is a brief sketch of the proof of the fundamental theorem of arithmetic that is most commonly presented in textbooks.

1. First one introduces Euclid's algorithm, and shows that it leads to the following statement: for any two integers x and y there exist integers h and k such that hx+ky=(x,y), where (x,y) is the highest common factor of x and y.

2. Next, one deduces from this the result that if p is a prime and p divides ab then p divides a or p divides b. (Proof: if p does not divide a then (p,a)=1 so by the previous result we can find h and k such that hp+ka=1. Then hpb+kab=b. Since p divides ab and p obviously divides hpb, we deduce that p divides b.)

3. Then, one deduces from this, by an easy inductive argument,
that if p divides a_{1}...a_{k} then p divides
a_{i} for some i.

4. Lastly, one takes a supposed minimal counterexample to the
theorem. So let
p_{1}...p_{r}=q_{1}...q_{s}, where the
p_{i} and q_{j} are all primes and not the same ones
up to a reordering. By minimality, no p_{i} is equal to any
q_{j} (or we could divide through and get a smaller
example). But p_{1} divides the product of the p_{i}
and hence the product of the q_{j}. By Step 3, p_{1}
divides some q_{j}, which is nonsense as q_{j}
is a prime not equal to p_{1}.

If you did not know how to prove unique factorization, then what
would possess you to define Euclid's algorithm, think of the clever
trick to show Step 2 above, and put it all together? It seems that
Euclid himself did something like that. (Although he did not write
down a complete proof of unique factorization, he did get as far as
Step 2, and must have known how to deduce from it the whole theorem.)
Did he stumble on his ideas by accident, messing about with highest
common factors and suddenly noticing what he could do with his
results, did he start with the problem of unique factorization and
develop his algorithm to deal with it, or was he simply an utter
genius who could invent arguments of several steps all in one go? I am
no historian, and do not even know whether the answer to this question
is known. However, I hope to show that he * could * have been
led * naturally * to his famous algorithm by first thinking
about unique factorization. (I myself believe that he was led to it
this way, but as I say this does not matter.)

In the spirit of Polya, I shall try to make as explicit as possible the rules of thumb that I assume are part of a standard mathematical armoury. I shall probably be more explicit than Euclid himself would have been, but this is not a problem as I am not trying to be historical, and in any case it is quite possible to apply mathematical rules of thumb without ever being aware of them - just as it is possible to speak grammatically without formulating the rules of grammar. I shall give far more detail than any human reader is likely to need, because I am also interested in how one might teach computers to do mathematics.

One guiding principle is so useful and well known that I shall state it before I even start.

* For questions to do with the positive integers, induction is a
good idea. Very often, a good first line of an argument is, "Let
us consider a minimal counterexample". *

We can now get to work. Guided by Principle 1 above, we do
indeed consider a minimal counterexample. What does this mean?
Since it is a counterexample, it must be a pair of distinct
prime factorizations of the same number. Since it is minimal,
it should not be possible to find a smaller example. We must
therefore consider an expression
p_{1}...p_{r}=q_{1}...q_{s},
where the p_{i} and q_{j} are prime numbers,
and they are not the same sequence up to a reordering. Now
it is clear that we cannot just stare at this expression and
feel certain that it must be false. After all, why shouldn't
the two sides of the expression be equal if say the primes
involved are very large? We have to find some * reason
* for them not being equal, and we don't have much to
go on.

When you don't have much to go on, the following embarrassingly obvious principle is often useful.

* Write down what you do have to go on and see
what you can deduce from it. *

Is there anything we haven't used in this example? There is, because we have not yet used the minimality of the counterexample. How does one ever deduce anything from minimality? This question has an answer, which I shall formulate as another principle.

* If you want to exploit the minimality of an X, then think of
methods for finding a smaller X. Given that a smaller X does not
exist, any method you think of must fail. The fact that it fails
has consequences that may be useful. *

How might we pass from
p_{1}...p_{r}=q_{1}...q_{s}
to a smaller example? Well, both sides represent some positive
integer n, so a more general question is how we can pass from
a positive integer n to a smaller one. There are various methods,
such as subtracting 1, or subtracting other numbers. Notice,
however, that there is not a lot we can say about n-1. Let us
be guided by Principle 2, and ask ourselves what we know about
n. We could also use the following equally obvious principle.

* If you are trying to find an example of an X, then write down
what makes an X an X. *

In this case we are trying to find an integer smaller than
n that can be factorized in two different ways. Now notice that
n is not a specific integer like 1001, but is rather a
* hypothetical * integer, and all we know about it is
that it equals both p_{1}...p_{r} and
q_{1}...q_{s}, where these are themselves
hypothetical sequences of primes. This leads to another
principle.

* If you are going to use a hypothetical object X to construct
an object Y, then Y will itself be hypothetical and all you can
use to construct Y is the hypotheses about X. *

Putting together Principles 4 and 5 in our particular example,
we see that we are trying to construct from
n=p_{1}...p_{r}=q_{1}...q_{s}
a smaller integer which can also be written as a product of
primes in two different ways, and that all we have to help
us is the two ways of writing n.

* Relax the constraints. For example, if you are asked to do
two things at once, see if you can do one of them and then
build up to the second. *

We are trying to find an integer smaller than n which is a product
of primes in two different ways. Can we at least use n to find a
smaller integer which is a product of primes in * one * way?
Notice that it is important here to * use n * in a genuine
way. It is not good enough to say "what about the number 2?"
So for this we apply Principle 5, and finally notice (of course
actually we could have noticed this long ago, but I am trying
to minimize the human skills I assume) that
p_{2}...p_{r} is an integer smaller than n,
constructed using the properties of n, with a prime factorization.

We now return to the harder problem - constructing a smaller
integer with * two * prime factorizations. It is clear
that using the property n=p_{1}...p_{r} will not
be enough, as every integer has at least one factorization. It
is therefore very natural to consider a second integer, constructed
using the property n=q_{1}...q_{s}, namely the
integer q_{2}...q_{s}.

We have got somewhere, since we now have an attempted
construction of a smaller example. Indeed, we will have a smaller
example if p_{2}...p_{r}=q_{2}...q_{s}.
However, now (applying Principle 3) we remember that there is
no smaller example. It follows that our attempt did not succeed.
From this we deduce that p_{1} does not equal q_{1}.

Let us review the above argument, guided by the following principle.

* Having reached a mathematical conclusion, examine it carefully
to see which hypotheses were essential and which were incidental. *

In this case, one sees readily that it did not matter that we
considered p_{1} and q_{1}. Indeed, since these
are hypothetical primes about which we have said nothing, it is
clear that there is * no distinction * between any of
the p_{i} or q_{j}. Consequently, we can extend
our above reasoning to achieve the following conclusion: no
p_{i} is equal to any q_{j}.

[It is interesting to think about how a computer would have to be
set up in order to apply the reasoning of the above paragraph.
Perhaps it would regard {1,2,...,r} and {1,2,...,s} as indexing sets,
taking care to note that these indexing sets are sets and nothing
more. Or perhaps it would consider p_{i} and q_{j} in
the first place rather than p_{1} and q_{1}.]

We have made some definite progress, since we now know that no
p_{i} is equal to any q_{j}. However, at this point we
hit a brick wall: there still appears to be absolutely no reason for
the two products to be distinct, or any obvious way to find a smaller
example. In a situation like this, it is often a good idea to fall
back on the following principle, which I divide into two
subprinciples.

* a. Try to prove something more specific and thus easier.
*

* b. Try to prove the simplest non-trivial special case you can
find. *

What does a special case mean for our example? It surely does
not mean choosing a * particular * pair of products of
primes and proving that they are distinct. After all, that is
just a matter of numerical checking and it will tell us nothing.
(Perhaps it is not obvious in advance that it will tell us nothing,
since there might be interesting patterns in the digits of the
numbers arising in the calculations. However, if we searched for
such patterns we would not find them.)

Let us see where we stand and try to describe it precisely. If we
are faced with the expression
p_{1}...p_{r}=q_{1}...q_{s} and know
that no p_{i} is equal to any q_{j}, then we feel
there is nothing much to say because the statement is too general. If
on the other hand we substitute values for r, s and all the
p_{i} and q_{j}, then we can say something but we
learn nothing because the statement is too specific. A natural
next step is to try something in between. This had better be
stated as a principle.

* If two attempted arguments fail for opposite reasons, then
try to find an argument in between. *

What could that mean? It is not difficult to say in this case. We
had problems if we specified none of the primes, and we also had
problems if we specified all of them. So let us try specifying *
some * of them. The simplest way of doing so is to specify just
one. So let us choose a value for p_{1}. What value
should we try? Principle 8b seems to tell us that we should try
p_{1}=2.

Doing this, we can instantly deduce that none of the q_{j}
is equal to 2. We now seem to have a genuinely new problem to think
about, simpler than the original one. We must show that it is not
possible for
2p_{2}...p_{r} to equal q_{1}...q_{s}
if none of the q_{j} is equal to 2. Why might this be?

Well, a minimally competent human mathematician can see the answer
immediately: the left hand side is even and the right hand side is odd.
How might a computer discover this? It could proceed as follows. First,
it would reflect that it * must use * the information that
p_{1}=2, since that is all that separates us from the earlier,
hopeless looking situation. Next, it would reflect that it * must
use * the information that no q_{j} is equal to 2, since
if some q_{j} did equal 2 (which as we know contradicts the
minimality) then one could divide through and lose the information
that one of the p_{i} was equal to 2. It could then apply
the following principle.

* Try to use as little information as possible. In other words,
see how you get on with as few hypotheses as you can, and introduce
extra ones only if they are necessary. *

We have already picked out two hypotheses that must be used. Using just those leads to the following conjecture: if 2 is a factor of m and n is a product of primes not equal to 2, then m does not equal n.

Again, we human beings find this immediately obvious, because
primes not equal to 2 are odd. But what could cause a computer to notice
this? There are several possibilities, one of which is to appeal to
Principle 1 again: consider a minimal counterexample. This will be
an example of the form m=q_{1}...q_{s}, where m is
even and each q_{j} is a prime not equal to 2. The minimality
tells us (by similar reasoning to our earlier minimality argument)
that q_{1}...q_{s-1} does * not * give rise to
a counterexample. That is, it is not equal to an even integer. Let
us write a=q_{1}...q_{s-1}. Then a is not divisible
by 2, but aq_{s} is. What does this tell us?

It is time for another principle.

* Don't forget what it is you are trying to prove.
*

In this case, I mean not the conjecture recently stated, but
unique factorization. If unique factorization is true and 2 divides
q_{1}...q_{s}, then 2 must equal one of the
q_{j}. In our case, the only way it can happen is if it
equals q_{s}. Can we prove this? We are asking the following
question: if a is odd, q_{s} is prime and aq_{s} is
even, does it follow that q_{s}=2?

* Try the contrapositive. *

All right, if q_{s} is a prime not equal to 2 and a is
odd, does it follow that aq_{s} is odd? Well, what does it
mean to say that a is odd? The definition is that it is not divisible
by 2. However, another, more positive definition is that a can be
written 2b+1 for some integer b. [This would be a very low-level
thing for a computer to notice, but I don't immediately see how it
would do so.] Let us substitute this in to the expression
aq_{s}, to obtain
(2b+1)q_{s}=2bq_{s}+q_{s}. It is now an
easy exercise [I leave it to the reader to think about how the
computer would do it] to notice that this is odd if and only if
q_{s} itself is odd. However, we know it is even, so we
know that q_{s} is even, and hence equal to 2 as required.

We now review the above argument. We see that what we ended up
needing to prove was that if aq_{s} was even and a was odd,
then q_{s} was equal to 2. We did this by showing that
q_{s} was even, and deducing (from the fact that it was
a prime) that it was 2. Thus, the statement that led to our success
was the following: if a and b are odd, then ab is odd.

Having considered a special case, we now do the obvious thing.

* Once a special case is proved, try to generalize it. *

We have had some success starting with the assumption that
p_{1}=2. We could now see if we can do something similar
with the assumption that p_{1}=3. We would find that we
could: indeed, just as with 2, the statement we would end up needing
to prove would be that if neither a nor b is divisible by 3, then
ab is not divisible by 3. Inspired by the proof of this for 2,
we would write a=2x+1 or 2x+2 and b=2y+1 or 2y+2, check four cases
(only three if we are feeling clever) and discover that the statement
is true. We could then go on and prove similar statements for 5,7
and so on.

We would then find ourselves faced with the following problem.
For any * specific * prime p, we can prove, by a brute force
argument, that if p|ab then p|a or p|b. However, our argument does
not generalize. Still, we have at least formulated the lemma
that we want to prove, and we know that it implies the whole
theorem.

To a mathematician who had not seen a proof of this statement, it would be a formidable problem to find one. Getting to the stage of formulating the lemma is definitely the easier part of proving the fundamental theorem of arithmetic. Once the lemma is formulated, we again find ourselves in the situation with which professional mathematicians are all too familiar: there seems to be absolutely no reason for the statement to be true in general, and yet one believes that it is.

This kind of despair can be very productive, because it often
leads to Principle 2. If there is not much to go on, then in a sense
one's moves are forced, and that can make finding a proof (if it exists)
* easier * rather than harder. In this case, in a desperate
attempt to strengthen our hypotheses, let us apply Principle 1 again.
We would like to consider a minimal counterexample. Principle 3 then
tells us to start with a prime p dividing a product ab while dividing
neither of the factors, and to attempt to build out of it a smaller
example.

In this case, it is not immediately obvious how to find a smaller
example, so let us consider (guided by Principle 6) a more general
problem: how can one construct * any * other example from a
given one? That is, if p divides ab without dividing either a or b,
how can one find any other example of a prime q dividing cd without
dividing c or d? Let us try to do the simplest thing and just vary
one of the numbers p, a or b. A moment's thought makes it clear that
varying p is unlikely to be easy, so let us try to vary a.

We must convert a into a new number a' in such a way that p divides a'b and does not divide a'. Let us try adding something to a. Given that we know nothing about a except that it is not a multiple of p, if we want to preserve this property, then we ought to add a multiple of p. As an experiment, let us try a'=a+p. We find that a'b=(a+p)b=ab+pb which is a multiple of p, since ab is. We can obviously repeat this process, which shows that adding any multiple of p to a gives an integer a' such that p|a'b but p divides neither a' nor b.

Having had some success with addition, we could try multiplication. What happens if we replace a by ha? Well, we know that p divides hab, since it divides ab, but perhaps it divides ha. Of course, if p does not divide h, then we suspect that p will not divide ha either, but that is what we are trying to prove. But hang on! Our counterexample was supposed to be minimal, so as long as h is smaller than b we are all right. So we now have two methods of producing new examples: multiply by a number smaller than b, and add or subtract a multiple of p. The question now is: can we use these two processes to construct a smaller example?

Just to make things absolutely clear, here is the problem we are now considering: given a prime number p and a positive integer a, can we construct a smaller positive integer a' from a by a combination of adding multiples of p and multiplying by positive integers less than b? The argument that allowed us to multiply no longer works if we have already changed a, so we should first multiply by some h between 1 and b-1 and then add tp for some t. Thus, we can reformulate the question more precisely: does there exist an integer combination a'=ha+tp which is positive and smaller than a, with h positive and smaller than b? Of course, t will have to be negative.

The most obvious thing we could do is try subtracting p from a. If a is greater than p then this works. Hence, on the assumption that we have a minimal counterexample, we know that a is less than p.

To make any more progress, we must use h. We are a little bit worried about the condition that h is less than b, so we would like to keep it as small as possible. On the other hand, we obviously need t to be non-zero, which forces ha to be greater than p. So a natural choice for h is the smallest integer with this property. We are thus led to the following question: let p be a prime, let 0 < a < p and let h be the smallest integer such that p < ha. (It is not possible for p to equal ha since p is a prime and a clearly cannot equal 1 if p does not divide b.) Is ha-p smaller than a?

Remembering Principle 12, we consider the contrapositive: if ha-p is greater than or equal to a, does it follow that h is not the smallest integer such that p < ha? Clearly the answer is that h is not the smallest if and only if p < (h-1)a. But if ha-p is greater than or equal to a, then, rearranging, (h-1)a is greater than or equal to p and hence greater than p (again because p is prime and a is not 1).

Have we suddenly finished the proof? Yes, provided that the h we chose is definitely less than b. Now we are assuming that p|ab, so we know that ab=sp for some positive integer s. Since p is prime, we know that s cannot equal 1. It follows that ab is at least as big as 2p. On the other hand, since a < p, it is clear that ha is not as big as 2p (either by the argument that ha-p < a < p or simply because the first time you go above p you certainly don't jump as far as 2p). Therefore, h < b as desired, and the proof is complete.

Just a reminder of why the proof is complete: we started with a minimal counterexample and have used it to construct a smaller counterexample. This contradiction proves the lemma, and with it the theorem.

I should perhaps remark that the algorithm implicit in the above proof is not quite the same as Euclid's algorithm, since we write p=ha-a' rather than p=qa+a'. Moreover, we pass from the pair (a,p) to the pair (a',p) rather than the pair (a',a). These differences make the algorithm less efficient for finding highest common factors, but they introduce ideas that lead easily to the usual version of the algorithm.

As every mathematician knows, the order in which one thinks of a proof is not the order in which one writes it. These web pages are attempts to write proofs in their untidy, thinking order rather than their neat, logical order. This makes them more long-winded but perhaps easier to understand and memorize. Nevertheless, the process of reorganizing one's incoherent thoughts into a mathematics paper or textbook is an important one. Examining the above argument, one is naturally led to isolate Euclid's algorithm, as I hope to show.

The trouble with arguments that start, "Consider a minimal counterexample" is that they often hide an interesting inductive process, almost pretending that it doesn't exist. A curious computer would have been told the following principle.

* If you have proved an argument by deriving a contradiction
from the existence of a minimal counterexample, try rewriting the
proof by starting with any example, repeatedly applying the
method you used to construct a smaller example and seeing where
you end up. *

In our proof, we started with a triple (p,a,b) and built a new
triple (p,a',b), with 0 < a' < a and with a' of the form ha+tp. What
happens if we repeat this process? The first thing to observe is that
p and b are never altered, so let us forget about them for now. Where
will the process of replacing a end? Well, the only extra facts that
we used from time to time were that a was not equal to 1 and was not a
multiple of p. It follows that if a is not a multiple of p then the
process will end when we have created a new a that * does *
equal 1. This new a is created from the original one by a succession
of operations of the following form: multiply by some h and subtract
some multiple of p. Doing two such operations results in doing a
third: k(ha+tp)+up=(kh)a+(kt+s)p. Hence, we have managed to express 1
as an integer combination Ha+Tp for some integers H and T. This is
exactly the consequence of Euclid's algorithm used in the usual
proof.

Now recall why it was that a should not equal 1. It was
because if p divides ab and a=1, then p certainly divides b.
But the whole point of the integer combination Ha+Tp was that
* if * p divides ab without dividing either a or b, then
it also divides (Ha+Tp)b without dividing Ha+Tp or b. Now let
us assume merely that p divides ab without dividing a. Then
we can find H and T such that Ha+Tb=1, and we know that we
will now find that p divides b if we continue the argument.
Let us do so: we know that Ha+Tp=1 and p divides (Ha+Tp)b.
Thus p divides b.

This is almost the argument in its standard form, but in order to prove that p divides (Ha+Tp)b we have used the fact that Ha+Tp was built in several steps from a. It is natural to ask whether we can prove it more directly, and as soon as we have asked that, we see that we can since p divides ab and p divides itself. We have recovered the trick used in step 2 of the usual proof.

We haven't quite formulated Euclid's algorithm, since we assumed that p was prime, but it is a short step from here to asking the question, "What would happen if we did the same process starting with an arbitrary pair of integers?" Given that we have now proved the fundamental theorem of arithemetic, we can quickly discover the answer, and then, if we feel like it, we can prove this answer by generalizing the proof for p prime and not using the fundamental theorem of arithmetic after all.