Theorem 9.6.1. The fundamental theorem of arithmetic.
If \(n \gt 1\) is an integer, then it can be written as a product of primes in exactly one way (up to permutations of the primes).
Section 9.6 Uniqueness of prime factorisation
Prime numbers follow very quickly when we learn about multiplication. Soon after that we realise that every positive integer can be written as a product of primes.
109
If this author is remembering back that far correctly…
\begin{equation*}
30 = 5 \times 3 \times 2
\end{equation*}
While we can shuffle those numbers around
\begin{equation*}
30 = 2 \times 5 \times 3 = 3 \times 2 \times 5 = \text{ etc}
\end{equation*}
those products will still contain the same number of each prime. Hence we can write it uniquely by putting the primes in order, smallest to largest:
\begin{equation*}
30 = 2 \times 3 \times 5.
\end{equation*}
This unique factorisation of integers into primes is called the “Fundamental theorem of arithmetic”, and seems so obvious to us that it is hard to imagine that one even has to prove it! However, while it feels obvious, it needs a proof.
110
Of course we have to make exceptions for zero and one, which are not primes. We also have to agree that when we factor a negative integer we just put a “\((-1)\times\)” and then factor the absolute value as usual.
The history of the theorem is not quite as direct as one might think. The result follows quite directly from the results of Euclid we discussed in the previous section, but does not actually appear explicitly in Euclid’s Elements. The 13th Century Persian mathematician al-Farisi proved that numbers can be decomposed as products of primes, but not the uniqueness of that decomposition. Prestet, Euler and Lagrange all seem to have been very close to writing it down, but it was actually Gauss who first wrote it down explicitly in 1801.
111
The interested reader can find out more about the history of this result using their favourite search-engine. A very good starting point is this article. It certainly surprises this author that the first explicit formal statement and proof of this fact comes a full century after Newton and Leibniz developed calculus.
112
Kamal al-Din al-Farisi (1265 – 1318) was a Persian mathematician and physicist who is also famous for his mathematically rigorous description of the formation of rainbows.
113
Jean Prestet (1648–1690), Leonard Euler (1707 – 1783) and Joseph-Louis Lagrange (1736 –1813). The latter was born Giuseppe Ludovico De la Grange Tournier. Your favourite search engine will get you to much more information, especially about Euler and Lagrange.
114
Johann Carl Friedrich Gauss (1777 – 1855) made an incredible number of contributions to mathematics and physics. Indeed, we have already come across him in this text back when we were busy computing \(1+2+\cdot+n\text{.}\) His history is well worth a quick trip to your favourite search engine.
With our work in the previous section we are ready to prove this result. It follows quite directly from Euclid’s lemma Lemma 9.5.9. Recall that this tells us that
\begin{equation*}
(p \mid ab) \implies (p\mid a) \lor (p \mid b).
\end{equation*}
Proof.
Let \(n \in \mathbb{Z}\) so that \(n \geq 2\text{.}\) We use induction to prove that \(n\) can be decomposed as a product of primes. We then show that this decomposition is unique.
We proceed to show the existence of a prime factorisation by strong induction 7.2.2.
-
Base case. Since \(n=2\) is prime, it is trivially written as a product of primes.
-
Inductive step. Assume that the result holds for all integers \(2 \leq k \lt n\text{.}\) If \(n\) is prime the result holds since the factorisation is trivial. On the other hand, if \(n\) is not prime, then (by definition) it can be written as\begin{equation*} n = ab \qquad \text{with } 1 \lt a,b \lt n. \end{equation*}Since \(a,b \lt n\) we know, by assumption, that\begin{equation*} a = p_1 p_2 \cdots p_k \qquad \text{ and } \qquad b = q_1 q_2 \cdots q_\ell \end{equation*}where the \(p_i, q_j\) are all primes. Hence\begin{equation*} n=ab=p_1 p_2 \cdots p_k \cdot q_1 q_2 \cdots q_\ell \end{equation*}is a product of primes as required.
We must now show that the decomposition is unique. A very standard way to show the uniqueness of a mathematical object is to assume there are two of them and show that the two must be equal. So, let us assume that we can write (please forgive recycling of \(p\)’s and \(q\)’s from just above):
\begin{equation*}
n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_\ell
\end{equation*}
If there are any common prime factors between the sides, then divide through by them. Now either that cancels all the factors (in which case we are done), or we are left with an expression as above but with no common factors on each side. Well then take the smallest remaining prime on either side, call it \(z\text{.}\) Since \(z\) divides one side, it must, by Euclid’s lemma, divide one of the factors on the other. However, since all the factors are prime, the factor \(z\) must be on both sides. But this cannot happen since we removed all the common factors. Thus the two factorisations of \(n\) must actually be the same.
