Now, we're almost ready to prove the Fundamental Theorem of Arithmetic. Since the theorem claims that prime factorizations are unique, we will prove this in two parts, as is usual for uniqueness proofs. First we prove the fact that we can factor numbers into primes (existence) and then show that this factorization is unique.
Every natural number $n \gt 1$ can be written as a product of primes.
We will prove that for $n \gt 1$, $n$ can be written as a product of primes via strong induction on $n$.
Base case. Let $n = 2$. Then 2 is a product of primes because 2 is a prime number.
Inductive case. Let $k \in \mathbb N$. Assume that for all natural numbers $m$ with $2 \leq m \leq k$, that $m$ can be written as a product of primes. We want to show that $n = k+1$ can be written as a product of primes. There are two cases to consider.
Notice that this is a more substantial use of strong induction than what we did for the proofs involving Fibonacci numbers. With the Fibonacci numbers, we know that we needed a fixed number of predecessor cases (the two right before). Here, we are in a situation where the required predecessor cases can be anywhere from 2 to $k$.
This also says something interesting about the structure of natural numbers. Right at the beginning, we had a very strict and fundamental definition for the natural numbers with zero and the successors. Now, knowing a few more things about natural numbers and integers allows us to have a more rich, but still recursive, construction—they're made up of prime numbers.
You will find such constructions in computer science. For example, insertion sort (see: Python (141), Racket (151)) is a sorting algorithm that is based on the recursive definition of a list. One can think of this as what we do with ordinary mathematical induction: it's induction on the basic definition of the structure.
But mergesort (see: Python (141), Racket (151)) is a more complicated algorithm that depends on splitting the list in half—this doesn't follow the definition of the list. In a sense, this is like strong induction: we assume that our program works on smaller pieces, not just the piece that comes right before it. Reasoning about algorithms like mergesort (which you'll see in 272) uses strong induction.
Now, we will finish the proof of the Fundamental Theorem of Arithmetic by showing that prime factorizations are unique. We use the usual strategy of considering two such factorizations and concluding they're actually the same.
By Theorem 8.1, 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$. Then by Euclid's lemma, $p_1 = q_j$ for some $j$. Now, we divide each factorization by $p_1$. 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.$$ But this is a smaller number with 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, we consider the number $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.