The basic theorem of arithmetic

The fundamental theorem of arithmetic tells us that every natural number greater than 1 can be uniquely decomposed into a product of primes. For example, the number 15 can be decomposed into the product of two primes 3 · 5, the number 30 can be decomposed into the product of three primes 2 · 3 · 5, and the number 16 can be decomposed into the product of four primes 2 · 2 · 2 · 2. Such a product of numbers is then called a prime decomposition. So we say that the prime decomposition of the number 10 is 2 · 5.

The prime numbers themselves have the simplest prime decomposition because we don't have to decompose them any further. The prime decomposition of 7 is simply 7.

Calculate the prime decomposition

What the fundamental theorem of arithmetic tells us

So the fundamental theorem of arithmetic, sometimes called the fundamental theorem of arithmetic, tells us two things:

• for any natural number greater than 1, we are able to find the prime decomposition,
• every number has exactly one unique prime decomposition.

Let's prove that this is indeed the case.

Proof of existence

First, we prove that for every natural number greater than 1, there is indeed at least one prime decomposition. We will use mathematical induction to do this. The first step of mathematical induction is to say that the smallest natural number that is greater than 1, that is, the number 2, is prime.

Now we will show that since we have a sequence of numbers 2, …, n, for which a prime decomposition can be found, if we add the number n + 1 to this sequence, then there is a prime decomposition for this new number using the primes from the sequence 2, …, n. Let's first show this with an example.

At the beginning, our sequence 2, …, n is a bit deformed because it contains only one number, the number 2. We say that if we add the number n + 1, i.e., the number 3, to this sequence, there will be a prime decomposition for this number. Since the number 3 is a prime number, of course there is a prime decomposition for it - it is the number 3.

Our sequence 2, …, n now has two members: 2, 3. Let's add the number 4 to the sequence. The number 4 is not a prime number, so it must decompose into the product of two other natural numbers that are greater than 1 but less than 4. But all such numbers are part of our sequence! And yet, only numbers that have prime decomposition are in this sequence! Thus, even the number 4 must have a prime decomposition: 2 · 2.

Going back to the general proof, we can write that the number 2 is prime and therefore has a prime decomposition. Suppose now that every number in the sequence 2, …, n can be prime decomposed - this is our inductive assumption. Then either the number n + 1 is prime and thus can be trivially decomposed into primes or it is a composite number. Thus, for this number, there must exist numbers a, b such that

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

while it must be the case that these natural numbers are naturally less than n + 1 and greater than 1:

$$\begin{eqnarray} a > 1,&\quad&a < n+1 \\ b > 1,&\quad&b < n+1 \\ \end{eqnarray}$$

The numbers a, b must thus be part of the sequence 2, …, n. But in doing so, for every number in this sequence there is a prime number decomposition (this is our inductive assumption), i.e. we can write

$$\begin{eqnarray} a&=&p_1\cdot p_2 \cdot \ldots \cdot p_i\\ b&=&q_1\cdot q_2 \cdot \ldots \cdot q_j\\ \end{eqnarray}$$

Where p_i and q_j are all prime numbers and p₁ · p₂ · … · p_i and q₁ · q₂ · … · q_j are thus their prime decompositions. But since we said that n + 1 is decomposable into the product n + 1 = a · b, then at the same time

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

So the number n + 1 is decomposable into the product of primes p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, so the newly added number n + 1 has a prime decomposition. It follows that every natural number greater than 1 has at least one prime decomposition.

Proof of uniqueness

Let us now show that for every natural number greater than 1 there are no more prime decompositions. We prove this theorem by means of a proof by contradiction. We will assume that the theorem is not true and hence we will assume that there exists a natural number n greater than 1 that has two distinct prime decompositions:

$$\begin{eqnarray} n&=&p_1\cdot p_2 \cdot \ldots \cdot p_i\\ n&=&q_1\cdot q_2 \cdot \ldots \cdot q_j \end{eqnarray}$$

We will also assume that of all the numbers that have multiple prime decompositions, n is the smallest. That is, there is no smaller natural number that has more than one prime decomposition. Since q₁ is one of the prime numbers that divides n, it must also be true, of course, that q₁ divides p₁ · p₂ · … · p_i.

Next, we must use Euclid's lemma. This says that if the prime number p divides the product of two integers a · b, then p also divides at least one of the numbers a or b. For example, the prime number 3 divides the number 84. We can decompose the number 84 into the product of the numbers 12 · 7. Euclid's lemma says that the prime number 3 divides at least one of the numbers 12 or 7 - in this case it divides the number 12.

Using this lemma, we can say that if q₁ divides p₁ · p₂ · … · p_i, then it must also divide at least one of the numbers p₁, p₂, … p_j. It can assume - without loss of generality - that q₁ divides the number p₁. Only that p₁ is also a prime number. When can a prime number divide another prime number? For example, what prime number is divisible by 7? Again, only the prime number 7. It can't divide another prime, because then it wouldn't be a prime. So it must be true that p₁ = q₁.

This means that there is one prime in both prime expansions that is the same: the prime p₁, and q₁. Let's divide both prime equations by p₁, and q₁, respectively:

$$\begin{eqnarray} \frac{n}{p_1}&=&\frac{p_1\cdot p_2 \cdot \ldots \cdot p_i}{p_1}\\ \frac{n}{q_1}&=&\frac{q_1\cdot q_2 \cdot \ldots \cdot q_j}{q_1} \end{eqnarray}$$

Since p₁ = q₁, we get the same number on the left side, let's denote it by m, for example.

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

On the right hand side, we just truncate the fractions:

$$\begin{eqnarray} m&=&p_2 \cdot p_3 \cdot \ldots \cdot p_i\\ m&=&q_2 \cdot q_3 \cdot \ldots \cdot q_j \end{eqnarray}$$

The number m is definitely a natural number that is smaller than n, because the number m was formed by dividing n by one of its prime factors. But on the right side of the equations, we have the prime factor of m in both cases. Thus, we were able to construct another number m, which is smaller than n and which also has two different prime decompositions. Which of course contradicts our assumption that n is the smallest number that has more than one unique prime decomposition.

So the only explanation is that there is no "smallest number with more than one prime decomposition". And that there is no "smallest number with more than one prime decomposition" means that there is no number with multiple prime decompositions - so every integer greater than one has exactly one unique prime decomposition.