CMSC 27100 — Lecture 12

Fundamental Theorem of Arithmetic (continued)

Theorem 12.1 (Euclid's Lemma). If $p$ is prime, and $a,b$ are integers such that $p \mid a \cdot b$, then $p \mid a$ or $p \mid b$.

Proof. Without loss of generality, suppose $p \not \mid a$. Then $\gcd(p,a) = 1$ and there exist integers $x$ and $y$ such that $xa + yp = 1$. Then multiplying both sides by $b$, we have $$b = xab + ypb.$$ Since $p \mid ab$, let $n$ be an integer such that $ab = pn$. Then we have $$b = xab + ypb = xpn + ypb = p \cdot (xn+yb).$$ Therefore, by definition of divisibility, $p \mid b$. $$\tag*{$\Box$}$$

Notice that this proof makes use of Bézout's lemma. Since Bézout's lemma appears about 2000 years after Euclid, it is safe to say that this is not the proof that appears in the Elements.

Now, we will prove the following lemma, which will allow us to prove the uniqueness part of the Fundamental Theorem of Arithmetic.

Lemma 12.2. If $p, p_1, \dots, p_k$ are prime and $p \mid p_1 \cdots p_k$, then $p = p_i$ for some $i$.

Proof. We will prove this by induction on $k$, the number of primes.

Base case. In this case, $p \mid p_1$. Since $p$ and $p_1$ are both prime, it must be the case that $p = p_1$.

Inductive case. Suppose our lemma is true for $k$ and consider $p \mid p_1 \cdots p_k \cdot p_{k+1}$. By Theorem 12.1, if $p \mid a \cdot b$, then $p \mid a$ or $p \mid b$. Let $a = p_1 \cdots p_k$ and $p_{k+1} = b$. If $p \mid a$, then $p = p_i$ for some $i$ with $1 \leq i \leq k$ by our inductive hypothesis and our result holds. If $p \mid b$, then $p = p_{k+1}$ and our result holds. $$\tag*{$\Box$}$$

Proof of Theorem 11.1.

Claim: $\forall~a,p_1,p_2,\dots,p_n,q_1,q_2,\dots q_m$ where every $p_i$ and $q_i$ is prime, if $$a = p_1p_2\dots p_n = q_1q_2 \dots q_m$$ then the $p_i$s and $q_i$s are the same.

We'll prove this by induction on $n$.

Our base case is where $n=1$. Since $p_1$ is prime, there can only be one $q_i$ and $q_i$ must equal $p_i$.

For the inductive case assume for all $a$, $p$s and $q$s, we have $a = p_1p_2\dots p_k = q_1q_2 \dots q_m$ implies the $p_i$s and $q_i$s are the same. Consider $a' = p_1p_2\dots p_kp_{k+1} = q_1q_2 \dots q_m$. Since $p_{k+1}$ divides $q_1q_2 \dots q_m$, there must be some $p_j$ such that $p_j = p_{k+1}$ by lemma 12.2. By our inductive hypothesis, $p_1p_2\dots p_k = q_1q_2 \dots q_{j-1}q_{j+1}q_m$ implies the $p_i$s and $q_i$s are identical. Hence multiplying both by $p_k+1 = q_j$ preserves the identity and demonstrates uniqueness.

Alternative Proof via minimality: 11.1a, 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 12.2, $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$}$

Euclid's Theorem

Theorem 12.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$}$