There is now a second version of this article I have written, which gives a simpler and more straightforward proof of the unique factorisation theorem.

Prerequisites

This article attempts to explain what is going on in the standard proof of the Fundamental Theorem of Arithmetic, a theorem which states that every natural number has a factorisation into primes which is unique except for ordering.

For example, 65790 = 2 × 3 × 3 × 5 × 17 × 43, and any other factorisation of 65790 into primes would have the same factors 2, 3, 3, 5, 17 and 43, except perhaps in a different order.

I assume that you know what a prime is (a number > 1 such that its only factors are itself and 1), and that you know the meanings of words like factor and multiple.

Proof That There is Any Factorisation into Primes

Before we prove that a factorisation into primes is unique, we really should prove that each number does have at least one factorisation into primes. But this is easy (or to use technical mathematical jargon, it is "obvious"):

Because the factors which multiply to make a number are always smaller than the number, this process has to stop somewhere.

For example, for N=65790:

This gives us the list of primes 5, 17, 2, 3, 3 and 43, which is the same as the list given previously, except the factors are in a different order.

We can see that choices were made when factorising the number in this way. What if we had made a different choice for a first factor of 65790, e.g. 258? It's not immediately obvious that different decompositions are going to result in the same final list of factors. Proving that the list is always the same is what the Fundamental Theorem is all about.

Euclid's Lemma

The critical element in the proof of the Fundamental Theorem is a lemma called Euclid's Lemma. (A lemma is a minor theorem which is useful only to help prove some other more important theorem. Sometimes a minor theorem is originally developed as a lemma, and then everyone decides that the lemma is actually quite important for it's own sake, but they keep on calling it a "lemma" anyway.)

Euclid's Lemma states that if a prime number p divides a number N (i.e. N is a multiple of p), and N is the product of two numbers a and b, then p must divide at least one of a or b.

To make this more concrete, I will state it in terms of a particular prime, for example 43. So: if 43 divides a number N, and N is the product of two numbers a and b, then 43 must divide at least one of a or b.

We can think of this as saying that there is a property of "forty-three-ness", which is possessed by any number that is a multiple of 43, and that if a number N has this property, and it is decomposed multiplicatively into two factors a and b, then the "forty-three-ness" will be found in at least one of those factors.

Think of a cake, with at least one raisin in it, which has the property of "raisin-containing-ness". If we cut the cake into two pieces A and B, at least one of those pieces must have a raisin in it. Now you might be thinking: what if the knife cuts the raisin in half? does that still count?, and to avoid that problem, we'll replace the raisins with marbles, and use a plastic knife, so that the knife can't possibly cut the marbles in half. (If we push this analogy too far, we'll eventually discover that the cake is made up entirely of marbles, and there isn't really any edible cake. But we haven't got there yet.)

What if I cut my cake into three pieces? Will there still be at least one marble in at least one piece? We can answer a definite yes by considering the division into three pieces to be a sequence of two divisions into two pieces. First there is a division into two pieces A and BC, and there must be at least one marble in at least one of A or BC. Then we cut BC into B and C, and if there was a marble in BC then there must now be a marble in at least one of B or C.

The same kind of extension holds for Euclid's Lemma. If a number N is a multiple of 43, and N is factorised into a × b × c, then at least one of a, b or c must be a multiple of 43. We apply the lemma first for the decomposition of N into a and b × c, and then we apply it a second time decomposing b × c into b and c.

(We still haven't proved Euclid's Lemma, but for the moment I am going to continue on the assumption that it has been proved.)

The Unique Factorisation Counter-Example

If unique factorisation didn't hold, then there would be a counter-example, which would consist of one number with two different factorisations into prime numbers, and not just different because the order is different.

For example, suppose that it was true that:

2 × 3 × 3 × 47 × 227 × 227 × 18651053 = 2 × 3 × 3 × 227 × 241 × 311 × 2654909

(It isn't true, but I'm just pretending, so I can show how we disprove the existence of the counter-example.)

The first thing we might notice is that both sides of this "equation" contain factors 2, 3, 3 and 227. So we should be able to simplify our equation by dividing both sides by these factors, which will leave us with:

47 × 227 × 18651053 = 241 × 311 × 2654909

in other words, an equation in which no prime occurs on both sides.

Now it gets exciting, because we can apply Euclid's Lemma to prove the impossibility of this equation. Just pick any prime number in the equation, for example 47. The left-hand side is a multiple of 47, which means that the right-hand side 241 × 311 × 2654909 must be a multiple of 47. But Euclid's Lemma tells us that this would mean that at least one of 241, 311 and 2654909 must be a multiple of 47. But this is impossible, because 241, 311 and 2654909 are all prime numbers and they are all different from 47, and prime numbers can only be multiples of 1 and themselves. Q.E.D. ("Q.E.D." is Latin for "I have finished my proof.")

Except that we haven't really QEDed, because we still have to prove Euclid's Lemma.

Proof of Euclid's Lemma

Remember that Euclid's Lemma says that:

If a number N is a multiple of a prime number p, and N = a × b, then at least one of a and b must be a multiple of p.

Another way to express this lemma is to state that there are no divisors of zero in arithmetic modulo p.

Just in case you don't know, I will give a brief explanation of modulo arithmetic. When I was in school, they taught us modulo arithmetic as clock arithmetic. For example, what is 3 hours after 11 o'clock? The answer is 2 o'clock, and this implies that 11 + 3 = 2. This equation makes sense if we qualify it by saying that it holds modulo 12, which is a short-hand for "ignoring multiples of 12".

What makes modulo arithmetic interesting is that it works consistently for addition, subtraction and multiplication. For example, if I pick any number equal to 11 modulo 12, such as 23 or 1727 or 120011, and add it to any number equal to 3 modulo 12, such as 15 or 144003 or even -21, then the answer will be equal to 2 modulo 12. The same applies to subtraction and multiplication: if we add multiples of 12 to the numbers being subtracted or multiplied, the answer will change by a multiple of 12, and will be the "same" modulo 12.

Addition, subtraction and multiplication are quite a large part of arithmetic, but what about division? The answer turns out to be that:

Division works properly for arithmetic modulo N, if and only if N is a prime number.

Showing that it does work properly for a prime number will turn out to be equivalent to Euclid's Lemma.

Showing that it doesn't work properly for a non-prime greater than 1 (i.e. a composite number) is actually quite easy (or obvious, to use technical mathematical jargon again).

For example, consider arithmetic modulo 10. Let's try dividing 6 by 2 modulo 10. It seems easy, because:

6 ÷ 2 = 3
But wait! We also have:
16 ÷ 2 = 8

which is a different answer modulo 10, even though the numbers being divided by (i.e. 6 and 16), were the same modulo 10. The cause of this "problem" is not hard to find: the difference between 16 and 6 is 10, which is the modulus, and 10 ÷ 2 = 5 because 2 × 5 = 10. This accounts for the two answers 3 and 8 differing by 5 even though they would have been the same if division modulo 10 worked properly. We call 2 and 5 zero divisors, because they divide into "zero" (modulo 10) and this happens because 2 and 5 are factors of the modulus.

So we can see that division cannot work in modulo arithmetic if the modulus isn't prime. But is it guaranteed to work if the modulus is a prime?

Proof that Arithmetic Modulo a Prime Number has no Zero Divisors

If a number a is a zero divisor in arithmetic modulo a prime number p, then a × b must be a multiple of p for some number b, where neither a nor b are equal to zero modulo p (i.e. neither is a multiple of p).

We want to show that this is impossible.

This first thing to do is to simplify the situation which we are trying to prove is impossible. We can subtract multiples of p from both a and b until they are both less than p (because this won't alter the fact that they multiply to make a multiple of p).

The next thing to do is to find a smaller a. Now if a was equal to 1, then we couldn't find a smaller a. But we already know that a can't be 1, because 1 × b = b, which wouldn't be a multiple of p.

So suppose that a is not equal to 1, but it has the property that a × b = 0 modulo p for some non-zero b. The smaller value of a that we want is the remainder after p is divided by a. This number is smaller than a, because remainders are always smaller than the number you are dividing by. And, it must have the property of being a zero-divisor. To show this, suppose that

p = a × x + r
where r is the remainder.

Then we can multiply this equation by b:

b × p = b × a × x + b × r

Now b × p is a multiple of p, and b × a × x must be a multiple of p because b × a is a multiple of p. Which means that b × r must be a multiple of p. We can think of r as inheriting the property of "being a multiple of p when multiplied by b" from a, where the inheritance occurs via the process of dividing the modulus by the divisor and keeping the remainder.

r is our "new" value for a. And we can repeat the process over and over again, each time inheriting the property of being a zero divisor of p. Since each new value is smaller than the previous value, we must eventually get a value of 1. Which we have already shown is impossible. So it must have been impossible for a to be a divisor of zero in our arithmetic modulo p.

Which means that division does work in arithmetic modulo p. (The technical jargon for this is that arithmetic modulo p is a field.)

Which means that Euclid's Lemma does hold true.

Which means that unique factorisation holds true. (So finally, Q.E.D.)

Post-logue

Mathematicians used to think that unique factorisation was true in any mathematical system which had the basic operations of addition, subtraction and multiplication, and a notion of prime numbers. But they eventually realised the importance of Euclid's Lemma, and its dependence on a notion of division by remainder, where the remainder is "smaller" in some sense that the divisor.

Systems with addition, subtraction and multiplication are called rings (in saying that I have glossed over a few technical issues), and one way to make interesting rings which are different from the ring of integers is to extend the ring of integers by adding in the square root of one particular number, like the square root of 2, or even the square root of -1. (In an extension, you include the new number, and all combinations of the new number via arithmetical operations with the existing numbers.) You can also extend with cube roots, and other sorts of roots. Some of these extensions have versions of Euclid's Lemma, which implies unique factorisation into primes, and some of them have unique factorisation even though they don't have Euclid's lemma, and some of them don't have unique factorisation at all.