The Fundamental Theorem of Arithmetic states that every natural number (greater than or equal to ) may be expressed as a product of prime numbers, and the product is unique up to reordering.

This theorem is one of the main reasons $1$ is not considered to be prime: indeed, if it were prime then $3 \times 5$ could be factorised into primes as $3 \times 5 \times 1$ , but these would be two different factorisations of the number $15$ . The FTA's statement is much cleaner if $1$ is not thought of as prime.

In a more general context, the FTA says precisely that the ring $Z$ is a unique_factorisation_domain; there is therefore a much more abstract proof than the elementary one we will present further on in this article:

$Z$ is a Euclidean domain (with Euclidean function given by "take the modulus");

Therefore $Z$ is a principal ideal domain (proof);

And principal ideal domains are unique factorisation domains (proof).

Examples

The FTA does not talk about $0$ or $1$ ; this is because these numbers are conventionally considered neither prime nor composite.

Even if we haven't bothered to calculate $17 \times 23 \times 23$ , we can immediately say that it is odd. Indeed, by the FTA, $2$ cannot divide $17 \times 23^{2}$ , because the complete list of prime factors of this number is ${17, 23, 23}$ , and $2$ is prime.

Proof

Timothy Gowers has an excellent article about the proof of the FTA.

The FTA consists of two parts: we must show that every number can be decomposed as primes, and also that every number can be decomposed uniquely.

Every number can be written as a product of primes

This part is the easier, and it uses strong_induction (a version of proof by induction).

Clearly $2$ can be written as a product of primes, because it is prime; so it can be written as just itself.

Now, for $n$ bigger than $2$ , if $n$ is prime then we are immediately done (just write it as itself). Otherwise, $n$ is not prime, so it can be written as $a \times b$ , say, with $a$ and $b$ both less than $n$ .

But by the inductive hypothesis, we can express $a$ and $b$ each as products of primes, so we can express $n$ as the combined product of the two sets of factors of $a$ and $b$ .

Example

Consider $n = 1274$ . We have two options: $n$ is prime or $n$ is composite.

It turns out that $n$ is actually equal to $49 \times 26$ , so it's not prime.

By the inductive hypothesis, we can factor $49$ as a product of primes (indeed, it's $7^{2}$ ); and we can factor $26$ as a product of primes (indeed, it's $2 \times 13$ ); so we can factor $1274$ as $2 \times 7^{2} \times 13$ .

(If you like, you can view this as just "start again at $49$ instead of at $1274$ , and spit out what you get; then start again at $26$ instead of $1274$ , and spit out what you get; and finally combine the spittings-out"; no mention of a spooky "inductive hypothesis" at all.)

Note that at this point, we haven't any guarantee at all that this is the only prime factorisation; all we assert so far is that it is a prime factorisation.

Every number can be decomposed uniquely as a product of primes

For this, we will need a basic (but non-obvious and important) fact about the behaviour of prime numbers: Euclid's lemma, which states that if a prime $p$ divides a product $a b$ , then $p$ divides at least one of $a$ and $b$ .

We will work by induction on $n$ again. If $n = 2$ then the result is immediate: a number can only be divided by numbers which are not larger than it, but $1$ and $2$ are the only such numbers.

Suppose $n$ can be written as both $p_{1} p_{2} \dots p_{r}$ and $q_{1} q_{2} \dots q_{s}$ , where each $p_{i}$ and $q_{j}$ is prime (but there might be repeats: maybe $p_{1} = p_{2} = q_{3} = q_{7}$ , for instance). We need to show that $r = s$ and that (possibly after reordering the lists) $p_{i} = q_{i}$ for each $i$ .

Certainly $p_{1}$ divides $n$ , because it divides $p_{1} p_{2} \dots p_{r}$ . Therefore it divides $q_{1} q_{2} \dots q_{s}$ , and hence it divides one of $q_{1}$ or $q_{2} \dots q_{s}$ , by Euclid's lemma. Therefore either it divides $q_{1}$ , or it divides one of $q_{2}$ or $q_{3} \dots q_{s}$ ; by induction, $p_{1}$ divides some $q_{i}$ . Because we don't care about the ordering of the list, let us reorder the list if necessary so that in fact $i = 1$ : put the factor $q_{i}$ at the start of the list.

Now, $q_{1}$ is prime, and $p_{1}$ is not equal to $1$ but it divides $q_{1}$ ; hence $p_{1} = q_{1}$ .

Dividing through by $p_{1}$ , then, we obtain $p_{2} \dots p_{r} = q_{2} \dots q_{s}$ , a strictly smaller number; so by the inductive hypothesis, $r - 1 = s - 1$ (so $r = s$ ) and the unordered list of $p_{i}$ is the same as the unordered list of $q_{i}$ for $i \geq 2$ .

This proves the theorem.

Why is this not obvious?

Timothy Gowers has a good piece on why this result is not just obvious. Of course, what is "obvious" and what is not "obvious" varies heavily depending on who you're talking to. For this author personally, the true reason it's not obvious is Gowers's reason number 4: because there are very similar structures which do not have the property of unique factorisation. (Gowers uses $Z [\sqrt{- 5}]$ ; on the page on irreducibles, we show that $Z [\sqrt{- 3}]$ could be used just as well.)

LESSWRONG
LW