There Are Infinitely Many Primes

Each number on the left in the following table is prime. We will see soon that this pattern does not continue indefinitely, but something similar works.

$$3 = 2+1$$

$$7 = 2\cdot 3 + 1$$

$$31 = 2\cdot 3 \cdot 5 + 1$$

$$211 = 2\cdot 3 \cdot 5 \cdot 7 + 1$$

$$2311 = 2\cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1$$

Theorem 1.2 (Euclid)   There are infinitely many primes.

Proof. Suppose that $p_1, p_2, \ldots, p_n$ are $n$ distinct primes. We construct a prime $p_{n+1}$ not equal to any of $p_1,\ldots, p_n$ as follows. If

$$N=p_1 p_2 p_3 \cdots p_n + 1,$$ (1.2.1)

then by Proposition 1.1.20 there is a factorization

$$N = q_1 q_2 \cdots q_m$$

with each $q_i$ prime and $m\geq 1$ . If $q_1 = p_i$ for some $i$ , then $p_i\mid{}N$ . Because of (1.2.1), we also have $p_i\mid{}N-1$ , so $p_i\mid{} 1=N-(N-1)$ , which is a contradiction. Thus the prime $p_{n+1} = q_1$ is not in the list $p_1,\ldots, p_n$ , and we have constructed our new prime. $\qedsymbol$

For example,

$$2\cdot 3 \cdot 5 \cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59\cdot 509.$$

Multiplying together the first $6$ primes and adding $1$ doesn't produce a prime, but it produces an integer that is merely divisible by a new prime.

Joke 1.2 (Hendrik Lenstra)   There are infinitely many composite numbers. Proof. To obtain a new composite number, multiply together the first $n$ composite numbers and don't add $1$ .