# Proof of the Unique Factorisation Theorem

## © Stu Savory, 2006.

**S**
o we were eating out at the pub for a geek booze-up and dinner, where Schorsch^{*}
had ordered a prime
rib for dinner. So we got to talking about prime numbers - as geeks are prone to do -
and ended up drawing a large
Sieve of Archimedes all over the paper tablecloth,
just to show Jen^{*} how it works :-)
Prime numbers are divisible only by themselves and one, there are no other factors.
Composite numbers are the product of prime factors (see below). Examples are :-
- 30 = 2*3*5
- 31 = 1*31, so 31 is prime
- 32 = 2*2*2*2*2 = 2
^{5} ; High five, Borat!
- 33 = 3*11
- 34 = 2*17
- etc etc.

Between drinks, I mentioned that *EVERY natural number ***N**
can be written as a unique product of prime numbers
, this is known as the Unique Factorisation Theorem (if there are only two factors, namely
**N** and one, then **N** is called prime).

Jen asked "Can you prove that?". Which I duly did, and now I'm reproducing my
(actually Euclid's) proof
here today for the edification of y'all, dear blogreaders :-)

This is a proof by contradiction, so let us assume that there might indeed be
positive non-prime (=composite) integers that you CAN'T write as the product of primes.
Let's arbitrarily call the smallest such integer **S**. Now **S** can't be prime or
one, by our definition, so we can write **S** as the composite **S = A * B**.
Because **S** has been defined as the smallest number which cannot be written as a
product of primes , both **A** and **B** CAN be written as products of primes.
It now follows that **S = A * B** can be written as a product of primes as well,
which leads to a contradiction. Therefore the assumption is wrong and
*every natural number ***N**
can be written as a unique product of prime numbers,
which is the Unique Factorisation Theorem. Since multiplication is
commutative^{**}, the order of the factors doesn't matter. So conventionally we
sort the factors in increasing order, as in the examples above, hence the *unique* factorisation.

Q.E.D.

BTW: It is because of the Unique Factorisation Theorem that you only need to look for
divisibility by primes
when checking to see if a number is composite or prime.

In a geometrical analogy, you can think of the real numbers as points along a line,
conventionally drawn horizontally. The integers are the points at unit distance from
their predecessor. And the primes are the points not overlapped by multiples
of any other (prime) integers, except 1. There now, that wasn't too hard, was it ? :-)

^{*} Names changed to protect them from the charge of ungeekiness ;-)

^{**} Yes I do know that there are certain algebraic rings for which the
Unique Factorisation Theorem does not hold, but that's too deep for this blog.

Now go visit my blog please, or look at other interesting maths stuff :-)