Now, we're almost ready to prove the Fundamental Theorem of Arithmetic. There are two parts to this. We'll first prove the fact that we can factor numbers into primes and then show that this factorization is unique. The proof of prime factorization involves an alternate form of mathematical induction which we'll call strong induction.
First, let's think about the problem. We want to show that every natural number $n$ has a prime factorization. So assuming that we set everything up properly, we make our hypothesis, that if $n$ has a prime factorization, then $n+1$ has a prime factorization. So we consider $n+1$. If it's prime, then we're good. If it isn't, then we observe that $n+1 = ab$ for some natural numbers $a$ and $b$. What we want is that we can apply our inductive hypothesis to $a$ and $b$. However, our inductive hypothesis doesn't quite say what we want: it says specifically that $n$ has a prime factorization, not $a$ or $b$!
Strong induction is a reformulation of induction that gives us a "stronger" hypothesis to say these kinds of things.
Definition 8.1. Let $\varphi(n)$ be a statement that depends on $n \in \mathbb N$. If
are both true, then the following is true:
This is called the principle of strong induction.
What is the difference between ordinary mathematical induction and strong induction? Or, in other words, what makes strong induction strong? The hypothesis that we make in each of our implications is stronger. Recall that ordinary induction was stated as a chain of implications $\varphi(k) \rightarrow \varphi(k+1)$. Strong induction is a chain of implications of the form $$\varphi(0) \wedge \varphi(1) \wedge \varphi(2) \wedge \cdots \wedge \varphi(k) \rightarrow \varphi(k+1).$$ Then what we're really proving is all of the following statements, \begin{align*} &\varphi(0), \\ \varphi(0) \rightarrow &\varphi(1), \\ \varphi(0) \wedge \varphi(1) \rightarrow &\varphi(2), \\ \varphi(0) \wedge \varphi(1) \wedge \varphi(2) \rightarrow &\varphi(3), \\ & \vdots \end{align*}
It's important to note that strong induction is not stronger in the sense that it allows us to prove things that we wouldn't be able to with mathematical induction. This is why I described strong induction as an alternate form of mathematical induction. It is possible to use mathematical induction to prove anything we would prove with strong induction, but this involves slightly altering the statement that you want to prove to incorporate your stronger assumptions.
A proof by strong induction looks similar to a proof by mathematical induction.
Theorem 8.2. Every natural number $n \gt 1$ can be written as a product of primes.
Proof. We will prove that for $n \gt 1$, $n$ can be written as a product of primes via strong induction on $n$.
Base case. $n = 2$. Clearly, 2 is a product of primes because 2 itself is a prime number.
Inductive case. Assume that for $2 \leq m \lt k$, $m$ can be written as a product of primes. We want to show that $k$ can be written as a product of primes. There are two cases to consider.
Now, we will finish the proof of Theorem 7.1 by showing that prime factorizations are unique.
Proof of Theorem 7.1. By Theorem 8.2, every natural number $n \gt 1$ has a prime factorization. Suppose that prime factorizations are not unique. 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$. Clearly, $p_1 \mid n$. Then by Lemma 7.6, $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$. $\tag*{$\Box$}$
The following result is another of Euclid's from the Elements.
Theorem 8.3 (Euclid's Theorem). There exist infinitely many primes.
Proof. Assume for a contradiction that there are only finitely many primes $p_1, p_2, \dots, p_k$. Consider $n = p_1 \cdot p_2 \cdots p_k + 1$. Since $n \gt p_i$ for all $i$, it cannot be a prime. Observe that for each prime $p_i$, we can write $n = q \cdot p_i + 1$ for some integer $q$.
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. 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. $\tag*{$\Box$}$
Definition 8.4. We define the factorial function $n!$ recursively by
The following result is called Wilson's Theorem, because it was stated by John Wilson in the 1700s. It turns out that it was stated around 700 years prior by an Arab mathematician, Hasan Ibn al-Haytham.
Theorem 8.5 (Wilson's Theorem). For all primes $p$, $(p-1)! = -1 \pmod p$.
Proof. Consider the equation $x^2 = 1 \pmod p$. We can rewrite this as $x^2 - 1 = 0 \pmod p$ and factor it to get $(x+1)(x-1) = 0 \pmod p$. Then $p \mid (p+1)(p-1)$ and therefore, $p \mid (p+1)$ or $p \mid (p-1)$. Thus, $x+1 = 0 \pmod p$ or $x-1 = 0 \pmod p$ and therefore $x = \pm 1 \pmod p$.
This means that for $2 \leq x \leq p-2$, $x \neq x^{-1} \pmod p$. Since each element has a multiplicative inverse and the inverses are unique, each of $2, 3, \dots, p-2$ can be paired with its inverse to cancel out to 1. Thus, we have $$1 \cdot 2 \cdot \cdots \cdot p-2 \cdot p-1 = 1 \cdot p-1 = 1 \cdot -1 = -1 \pmod p.$$ $\tag*{$\Box$}$
The following theorem is due to Pierre de Fermat, which is called Fermat's Little Theorem, to distinguish it from the more famous Fermat theorem, Fermat's Last Theorem (there are no integers $a,b,c$ such that $a^n + b^n = c^n$ for $n \gt 2$). Much like Fermat's Last Theorem, Fermat stated the result in the mid 1600s but declined to give a proof of it because the proof was "too long".
While it would be about 400 years before Fermat's Last Theorem gets proven (by Andrew Wiles in 1995), Fermat's Little Theorem was proved only about 100 years later, by Leonhard Euler. The following proof, using modular arithmetic, is due to James Ivory in the early 1800s and a bit later by Dirichlet.
Theorem 8.6 (Fermat's Little Theorem). For all prime numbers $p$ and integers $a$ such that $\gcd(a,p) = 1$, $a^{p-1} \equiv 1 \pmod p$.