Now, we will finish the proof of the Fundamental Theorem of Arithmetic by showing that prime factorizations are unique. We use a variant of the strategy we’ve seen before, where we assume that we have two such factorizations and showing they cannot be different by way of contradiction.
Before we get started, we will need a helpful property of primes, a result from Euclid’s Elements.
If $p$ is prime, and $a,b$ are integers such that $p \mid ab$, then $p \mid a$ or $p \mid b$.
If $p \mid a$, then we are done. Now, suppose $p \not \mid a$. We claim that $\gcd(p,a) = 1$. Since $p$ is prime, its only divisors are $1$ and $p$. Since $p \nmid a$, the only common divisor of $p$ and $a$ must be 1.
So by Bézout’s identity, there exist integers $x$ and $y$ such that $xa + yp = 1$. Multiplying both sides by $b$, we have $$b = xab + ypb.$$ Since $p \mid ab$, there exists an integer $n$ such that $ab = pn$. Then we have \begin{align*} b &= xab + ypb \\ &= xpn + ypb \\ &= p \cdot (xn+yb) \end{align*} Since $xn + yb$ is an integer, by definition of divisibility, $p \mid b$.
Notice that we begin the proof with an implicit use of LEM: we consider the two cases $p \mid a$ or $p \nmid a$. Now, if we are being technical, this does not exactly align with the $\vee e$ rule that we saw, which requires both cases to end at the same conclusion. If we examine this further, we notice that we don’t actually state the conclusion explicitly: in one case, we have $p \mid a$ and in the other case we conclude with $p \mid b$.
The actual conclusion we want is $p \mid a \vee p \mid b$. But how do we get there from our two different conclusions? Recall that the proposition $p \vee q$ means that at least one of $p$ or $q$ is valid. So if $p \mid a$ is true, then $p \mid a \vee \varphi$ will also be true for any proposition $\varphi$ that we wish. Similarly, if $p \mid b$ is true, then $\varphi \vee p \mid b$ will also be true.
This leads to the $\vee$-introduction rules: \[\begin{matrix}\displaystyle\frac{p}{p \vee q} \vee\!i &\text{and} &\displaystyle\frac{q}{p \vee q} \vee\!i.\end{matrix}\] In other words, if we prove $p$, then this is sufficient for a proof of $p \vee q$ for any $q$ and if we prove $q$, then this is a sufficient proof that $p \vee q$ for any $p$.
Note that this paritcular proof made use of Bézout’s lemma. Although Bézout’s lemma is attributed about 2000 years after Euclid, recall that result does actually appear in the Elements.
From Euclid’s lemma, we get the following extension, which follows via induction.
If $p, p_1, \dots, p_n$ are prime and $p \mid p_1 \cdots p_n$, then $p = p_i$ for some $i$.
Intuitively, this makes a lot of sense: if we express some integer as a product of primes and a prime divides this product, then our prime divisor is really one of the primes in the list.
Now, let’s prove uniqueness of prime factorizations.
By Theorem 9.5, every natural number $n \gt 1$ has a prime factorization. Suppose that prime factorizations are not unique, so some numbers may be written as a product of primes in more than one way. Let $n$ be the smallest number that doesn’t have a unique prime factorization, so $$n = p_1 \cdots p_k = q_1 \cdots q_\ell,$$ where $p_i$ is prime for $1 \leq i \leq k$ and $q_j$ is prime for $1 \leq j \leq \ell$.
We see that $p_1 \mid n$. This means that $p_1 \mid p_1 \cdots p_k$, which is clear, but this also means that $p_1 \mid q_1 \cdots q_\ell$. So by Euclid’s lemma, $p_1 = q_j$ for some $j$. Now, we consider each factorization with $p_1$ removed. This gives us $$\frac n {p_1} = p_2 p_3 \cdots p_k = q_1 q_1 \cdots q_{j-1} q_{j+1} \cdots q_\ell.$$ Since $p_1$ is a prime, this is a smaller number than $n$ and it has more than one prime factorization, contradicting the minimality of $n$.
The fact that every number can be factored into primes is a very useful property of numbers to have. The following result is another of Euclid’s from the Elements. You can tell that this one is very important because out of all the results of Euclid, this one is called Euclid’s Theorem.
There exist infinitely many primes.
Assume for a contradiction that there are only finitely many primes. Since there are finitely many, we can list them all: \[p_1, p_2, \dots, p_k.\] Now, let $n = p_1 \cdot p_2 \cdots p_k + 1$. Since $n \gt p_i$ for all $i$, it cannot be a prime—it is too big to be in our list from above.
Observe that for each prime $p_i$, we can write $n = q \cdot p_i + 1$ for some integer $q$—here, $q$ is the product of the other primes. By the Division Theorem, this means that we have a remainder of 1 when dividing $n$ by any of the primes $p_i$. Since $1 \neq 0$ and $1 \lt p_i$, it must be the case that $p_i$ does not divide $n$ for all $i$.
In other words, $n$ cannot be factored into primes, since none of the primes are factors of $n$. But this is a contradiction of the Fundamental Theorem of Arithmetic. Therefore, our assumption that there were only finitely many primes was incorrect and there must exist infinitely many primes.