Proofs from THE BOOK by Martin Aigner and Günter Ziegler begins by giving six proofs of the infinity of primes. The first proof is what they call “the oldest Book Proof” attributed to Euclid. Before we go over this proof, lets cover some background.

Definition 1 Let ${p\in\mathbb{N}}$ such that ${p\neq1}$. ${p}$ is called prime, if the only positive divisors of ${p}$ (i.e., ${m\in\mathbb{N}}$ such that ${m|p}$) is ${1}$ and ${p}$.

Definition 2 Let ${n\in N}$ such that ${n\neq1}$. ${n}$ is called composite, if ${n}$ is not prime.

Remark 1 In this note, a prime number is a natural number. So, ${p>1}$.

Here is a translation of the definition in terms of the GCD.

Lemma 3 Let ${n\in\mathbb{Z}}$ such that ${n\neq0}$ and ${p\in\mathbb{N}}$. If ${p}$ is prime, then ${gcd(n,p)=1}$ or ${gcd(n,p)=p}$.

Proof: Proof. Let ${n\in\mathbb{Z}}$ such that ${n\neq0}$ and ${p\in\mathbb{N}}$. Assume that ${p}$ is a prime number. Note that ${gcd(n,p)}$ divides ${p}$, and it is positive. Since ${p}$ is prime, we must have either ${gcd(n,p)=1}$ or ${gcd(n,p)=p}$. $\Box$

The next theorem is the fundamental connection between prime numbers and the divisibility relation among integers. The theorem is sometimes called Euclid’s First Theorem or Euclid’s Principle. A corollary is the Fundamental Theorem of Arithmetic or the Unique Factorization Theorem (Hardy and Wright 1979).

Theorem 4 (Euclid’s First Theorem) Let ${p\in\mathbb{N}}$ such that ${p\neq1}$. ${p}$ is prime iff, for any ${a,b\in Z}$ such that ${p|ab}$, we have ${p|a}$ or ${p|b}$.

Proof: (Implication) Let ${p\in\mathbb{N}}$ such that ${p}$ is prime. Let ${a,b\in\mathbb{Z}}$. Assume that ${p|ab}$. Note that if ${a=0}$, then ${p|a}$. Thus, assume further that ${a\neq0}$.
Now, if ${p|a}$, then we again have nothing to prove. So, assume that ${p\nmid a}$. Then ${gcd(p,a)=1}$. So, ${p|b}$ by the previous lemma.
(Converse) Let${p\in\mathbb{N}}$ such that ${p\neq1}$. Assume the condition: for any ${a,b\in\mathbb{Z}}$ such that ${p|ab}$, we have ${p|a}$ or ${p|b}$.
Let ${n\in\mathbb{N}}$ such that ${n|p}$. Our goal is to show that ${n=1}$ or ${n=p}$.
If ${n=1}$, then we have nothing to show; so, assume that ${n\neq1}$. Now, there is ${s\in\mathbb{Z}}$ such that ${p=ns}$. Since ${n,p\in\mathbb{N}}$, ${s\in\mathbb{Z}}$. Note that ${p|ns}$. So, ${p|n}$ or ${p|s}$. If ${p|s}$, then ${1 implies ${s. This is a contradiction, since ${p|s}$. So, ${p\nmid s}$. Thus, ${p|n}$ by the assumption. Thus, there is ${t\in\mathbb{Z}}$ such that ${n=pt}$. Note that ${t\in\mathbb{N}}$, since ${n,p\in\mathbb{N}}$. Since ${p=ns}$, we have ${n=nst}$. By the cancellation law, we have ${1=st}$; so, ${s=1}$ and ${t=1}$. Hence, ${n=p}$. $\Box$

Proposition 5 Let ${p,q\in\mathbb{N}}$ be distinct prime numbers, and ${x\in\mathbb{Z}}$. If ${p|x}$ and ${q|x}$, then ${pq|x}$.

Proof: Let ${p,q\in\mathbb{N}}$ be distinct prime numbers, and ${x\in\mathbb{Z}}$. Assume that ${p|x}$ and ${q|x}$. Then there is ${n\in\mathbb{Z}}$ such that ${x=pn}$. Since ${q|x}$, we have ${q|pn}$. So, ${q|p}$ or ${q|n}$. Since ${p}$ and ${q}$ are distinct primes, ${q\nmid p}$. This implies ${q|n}$. Thus, there is ${m\in\mathbb{Z}}$ such that ${n=qm}$. Hence, ${x=pn=p(qm)}$. Consequently, ${pq|x}$. $\Box$

We now like to present and prove the Unique Factorization Theorem. To do this, we need establish the following technical lemma.

Lemma 6 Let ${n\in\mathbb{N}}$ such that ${n\neq1}$. If ${p_{1},\cdots,p_{s}\in\mathbb{N}}$ are all primes such that ${p_{1}, ${q_{1},\cdots,q_{t}\in\mathbb{N}}$ are all primes such that ${q_{1}, a sequence of integers ${\alpha_{1},\cdots,\alpha_{s}\in\mathbb{N}}$, and a sequence of integers ${\beta_{1},\cdots,\beta_{t}\in\mathbb{N}}$ such that

$\displaystyle n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}=q_{1}^{\beta_{1}}q_{2}^{\beta_{2}}\cdots q_{t}^{\beta_{t}},$

then ${s=t}$ and ${p_{i}=q_{i}}$.

Proof: Let ${n\in\mathbb{N}}$ such that ${n\neq1}$. Assume that there are two sequence of primes ${p_{1} and ${q_{1}, and two sequences of natural numbers ${\alpha_{1},\cdots,\alpha_{s}}$ and ¯${\beta_{1},\cdots,\beta_{t}}$ such that

$\displaystyle n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}=q_{1}^{\beta_{1}}q_{2}^{\beta_{2}}\cdots q_{t}^{\beta_{t}}.$

Suppose that there is a prime that shows up in one of the list but not in the other. Say the prime ${p}$ shows up in ${p_{1}, but not in ${q_{1} (other case is verbatim). Since ${p|n}$, we have ${p|(q_{1}^{\beta_{1}}q_{2}^{\beta_{2}}\cdots q_{t}^{\beta_{t}})}$. Since ${p}$ is prime, ${p}$ must divide one of ${q_{i}}$. But this is a contradiction, since each ${q_{i}}$ is a prime different from ${p}$. Thus, all the primes showing up in one list must show up in the other. Hence, ${p_{1} and ${q_{1} are the same lists of primes. $\Box$

We are now ready to prove the Unique Factorization Theorem for natural numbers.

Theorem 7 (Unique Factorization Theorem) Let ${n\in\mathbb{N}}$ such that ${n\neq1}$. There are unique primes ${p_{1},\cdots,p_{s}\in\mathbb{Z}}$ such that ${p_{1} and unique sequence of positive integers ${\alpha_{1},\cdots,\alpha_{s}\in\mathbb{N}}$, such that

$\displaystyle n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}.$

Proof: We will prove this theorem by proving the existence of prime factorization first, then proving the uniqueness of the prime factorization.

Proof of existence. Let ${F}$ be the set of all positive integers strictly greater than ${1}$ (i.e., ${>1}$) that cannot be written as the product of primes (if ${p}$ is prime, then we count it as the “product” of a prime). Suppose ${F}$ is not empty. Then there is the least element ${l}$ in ${F}$.
Let ${n\in\mathbb{N}}$ such that ${n. Suppose ${n|l}$. Then ${l=nm}$ for some ${m\in\mathbb{N}}$. Since ${n}$ and ${m}$ are not in ${F}$ (it is smaller than ${l}$), ${n}$ and ${m}$ can be written as the product of primes. So, ${l}$ can be written as the product of primes. This is a contradiction. So, ${l}$ is not divisible by any number between ${1}$ and ${l}$. So, ${l}$ is a prime. This is a contradiction, since ${l\in F}$. Thus, ${F}$ is empty. Hence, every number can be written as the product of primes. $\Box$

Proof of uniqueness. Let ${n\in N}$ such that ${n\neq1}$. Assume that there are two sequences of primes ${p_{1} and ${q_{1}, and two sequences of positive integers ${\alpha_{1},\cdots,\alpha_{s}\in\mathbb{N}}$ and ${\beta_{1},\cdots,\beta_{t}\in\mathbb{N}}$ such that

$\displaystyle n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}=q_{1}^{\beta_{1}}q_{2}^{\beta_{2}}\cdots q_{t}^{\beta_{t}}.$

By the previous lemma, ${p_{1} and ${q_{1} are the same lists of primes. Thus, we now have

$\displaystyle n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}=p_{1}^{\beta_{1}}p_{2}^{\beta_{2}}\cdots p_{s}^{\beta_{s}}.$

Suppose ${i}$ is the smallest natural number such that ${\alpha_{i}\neq\beta_{i}}$. Suppose ${\alpha_{i}<\beta_{i}}$. Let ${k=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{i}^{\alpha_{i}}}$. Let ${m=\frac{n}{k}}$. Then

$\displaystyle m=p_{i+1}^{\alpha_{i+1}}p_{i+2}^{\alpha_{i+2}}\cdots p_{s}^{\alpha_{s}}=p_{i}^{\beta_{i}-\alpha_{i}}p_{i+1}^{\beta_{i+1}}\cdots p_{s}^{\beta_{s}}.$

But this contradicts the previous lemma, since ${p_{i}}$ does not show up in the list of primes ${p_{i+1}<\cdots for ${m}$, but does show up in the list ${p_{i}<\cdots for ${m}$. Similarly, ${\beta_{i}<\alpha_{i}}$ implies the same contradiction. Hence, there is no ${i}$ such that ${\alpha_{i}\neq\beta_{i}}$. Consequently, ${\alpha_{i}=\beta_{i}}$ for all ${1\leq i\leq s}$. $\Box$

We are now ready to prove Euclid’s Second Theorem, also called the Infinitude of Primes Theorem. It was proved by Euclid in Book IX Proposition 20 of the Elements.

Theorem 8 (Euclid’s Second Theorem) The number of primes is infinite.

Proof: (by contradiction) For any finite set ${\{p_{1},\cdots,p_{r}\}}$ of primes, consider the number ${n=p_{1}p_{2\cdots}p_{r}+1}$. This ${n}$ has a prime divisor ${p}$. But ${p}$ is not one of the ${p_{i}}$: otherwise ${p}$ would be a divisor of ${n}$ and of the product ${p_{1}p_{2}\cdots p_{r}}$, and thus also of the difference ${n-p_{1}p_{2}\cdots p_{r}=1}$, which is impossible. So a finite set ${\{p_{1},\cdots,p_{r}\}}$ cannot be the collection of all prime numbers. $\Box$