## Problem

#### Theorem (the Fundamental Theorem of Arithmetic)

Every integer greater than $1$ can be expressed as a product of primes. Moreover, this product is unique up to reordering the factors.

This is a really important theorem—that’s why it’s called “fundamental”! It tells us two things: existence (there is a prime factorisation), and uniqueness (the prime factorisation is unique). Both parts are useful in all sorts of places.

The existence part is useful because it tells us that the primes are somehow the “building blocks” from which all integers are made, and this helps with lots of things.

The uniqueness part is useful because it allows us to do certain things that would otherwise not be possible. For example, if we know the prime factorisation of $n$, then we know the prime factorisation of $n^2$, safe in the knowledge that $n^2$ can’t also have some other prime factorisation.

Note that the fundamental theorem of arithmetic is one good reason why it’s convenient to define $1$ not to be a prime. If it were prime, then we could include as many factors of $1$ as we liked in the prime factorisation of a number to get lots of different (but not interestingly different) factorisations.

The statements below can be sorted into a proof of the Fundamental Theorem of Arithmetic. You might want to print them out and cut them up to rearrange them.

To help, we’ve separated the two parts (existence and uniqueness), so you only need to shuffle statements within each part.

#### Existence

Every integer greater than $1$ can be expressed as a product of primes.

That is, there is a smallest number that doesn’t have a prime factorisation, say $n$.

So $n$ is composite, say $n = ab$ with $1 < a$, $b < n$.

Then there must be a minimal counterexample.

Any prime has a prime factorisation.

But then $n$ has a prime factorisation: the product of the prime factorisations of $a$ and $b$.

Suppose that the result is not true.

So there is not a counterexample—the result is true.

So $n$ is not prime.

Since $a$ and $b$ are smaller than $n$, they have prime factorisations.

(Remember that $n$ is the smallest number that doesn’t have a prime factorisation.)

#### Uniqueness

The product is unique up to reordering the factors.

Then we can cancel these primes from the products.

Say $n = p_1 \ldots p_k = q_1 \ldots q_l$, where $p_1$, …, $p_k$, $q_1$, …, $q_l$ are primes, not necessarily distinct.

Suppose that some number $n$ has two prime factorisations.

Since $p_1$, $q_1$, …, $q_l$ are prime, we must have $p_1 = q_r$ for some $r$.

So $p_1$, $p_2$, …, $p_k$ are in fact $q_1$, $q_2$, …, $q_l$ in some order.

We can continue in this way.

Then $p_1$ divides $q_1 \ldots q_l$ and $p_1$ is prime, so $p_1$ divides $q_1$ or $p_1$ divides $q_2$ or … or $p_1$ divides $q_l$.