The fundamental theorem of arithmetic

The fundamental theorem of arithmetic tells us that every positive integer greater than 1 can be written uniquely as a product of primes. For example, 15 is the product of two primes, 3 · 5, 30 is the product of three primes, 2 · 3 · 5, and 16 is the product of four primes, 2 · 2 · 2 · 2. Such a product is called a prime factorisation. So we say that the prime factorisation of 10 is 2 · 5.

The simplest prime factorisation belongs to the primes themselves, because we do not need to break them down any further. The prime factorisation of 7 is simply 7.

Work out a prime factorisation

What the fundamental theorem of arithmetic says

The fundamental theorem of arithmetic, also known as the unique factorisation theorem, tells us two things:

• for every positive integer greater than 1 we can find a prime factorisation,
• every number has exactly one prime factorisation.

Let’s prove that this really is so.

Proof of existence

First we prove that every positive integer greater than 1 really does have at least one prime factorisation. We will use proof by induction. The base case is that the smallest positive integer greater than 1, namely 2, is a prime.

Now we show that if we already have the numbers 2, …, n, each of which has a prime factorisation, then when we add the number n + 1 to them, this new number has a prime factorisation too. Let’s look at an example first.

At the start our list 2, …, n is a bit degenerate, because it contains just one number, 2. We claim that when we add n + 1, that is, the number 3, it will have a prime factorisation. Since 3 is a prime, it of course has one – it is 3 itself.

Our list 2, …, n now has two numbers: 2, 3. Let’s add the number 4. The number 4 is not a prime, so it must be possible to write it as a product of two other positive integers that are greater than 1 but less than 4. All such numbers are already in our list! And the list contains only numbers that have a prime factorisation! So 4 must have a prime factorisation too: 2 · 2.

Going back to the general proof, 2 is a prime and so it has a prime factorisation. Now suppose that every number in the list 2, …, n can be factorised into primes – this is our inductive hypothesis. Then n + 1 is either a prime, and so trivially a product of primes, or it is a composite number. In that case there must be numbers a, b such that

$$n+1=a\cdot b$$

and these positive integers must of course be less than n + 1 and greater than 1:

$$\begin{array}{rcl}a>1,& & a<n+1\\ b>1,& & b<n+1\end{array}$$

So a, b must be in the list 2, …, n. But every number in this list has a prime factorisation (that is our inductive hypothesis), so we can write

$$\begin{array}{rcl}a& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ b& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

where all the p_i and q_j are primes, and p₁ · p₂ · … · p_i and q₁ · q₂ · … · q_j are their prime factorisations. Since we said that n + 1 can be written as the product n + 1 = a · b, we also have

$$\begin{array}{rcl}n+1& =& a\cdot b\\ & =& p_1\cdot p_2\cdot \dots \cdot p_i\cdot q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

So n + 1 is a product of the primes p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, which means the newly added number n + 1 has a prime factorisation too. It follows that every positive integer greater than 1 has at least one prime factorisation.

Proof of uniqueness

Now let’s show that no positive integer greater than 1 has more than one prime factorisation. We will prove this by contradiction. We assume that the theorem is not true, so there is a positive integer n greater than 1 that has two different prime factorisations:

$$\begin{array}{rcl}n& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ n& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Let’s also assume that, of all the numbers with more than one prime factorisation, n is the smallest. That is, there is no smaller positive integer with more than one prime factorisation. Since q₁ is one of the primes dividing n, it must of course also divide p₁ · p₂ · … · p_i.

Next we need Euclid’s lemma. It says that if a prime p divides the product of two integers a · b, then p also divides at least one of a and b. For example, the prime 3 divides 84. We can write 84 as the product 12 · 7. Euclid’s lemma says that 3 divides at least one of 12 and 7 – in this case it divides 12.

Using this lemma, since q₁ divides p₁ · p₂ · … · p_i, it must also divide at least one of p₁, p₂, …, p_i. Without loss of generality we can assume that q₁ divides p₁. But p₁ is a prime too. When can a prime divide another prime? For example, which prime is divisible by the prime 7? Only 7 itself. A prime cannot divide a different prime, because then that one would not be a prime. So we must have p₁ = q₁.

This means both prime factorisations contain one prime that is the same: p₁ (or equivalently q₁). Let’s divide the two equations by p₁ and q₁ respectively:

$$\begin{array}{rcl}\frac{n}{p_1}& =& \frac{p_1\cdot p_2\cdot \dots \cdot p_i}{p_1}\\ \frac{n}{q_1}& =& \frac{q_1\cdot q_2\cdot \dots \cdot q_j}{q_1}\end{array}$$

Since p₁ = q₁, the left-hand sides are the same number. Let’s call it m. So

$$m=\frac{n}{p_1}=\frac{n}{q_1}$$

On the right-hand side we simply cancel the fractions:

$$\begin{array}{rcl}m& =& p_2\cdot p_3\cdot \dots \cdot p_i\\ m& =& q_2\cdot q_3\cdot \dots \cdot q_j\end{array}$$

The number m is certainly a positive integer and it is less than n, because we got it by dividing n by one of its prime factors. But the right-hand sides of both equations are prime factorisations of m. So we have built another number m, smaller than n, that also has two different prime factorisations. That contradicts our assumption that n is the smallest number with more than one prime factorisation.

The only explanation is that there is no “smallest number with more than one prime factorisation”. And if there is no such smallest number, then there is no number at all with more than one prime factorisation – every integer greater than 1 has exactly one prime factorisation.