Infinitude of Primes

The fact that primes never run out is one of the oldest and most celebrated results in mathematics.

Euclid's Theorem

Theorem (Euclid's Theorem)

[cite_start]There are infinitely many prime numbers[cite: 88].

Proof. Suppose there are only finitely many primes $p_{1}, p_{2}, \dots, p_{n}$ . Consider the number $N = p_{1} p_{2} \dots p_{n} + 1$ .

$N > 1$ , so it must have a prime divisor $q$ .
If $q$ were one of the $p_{i}$ , then $q$ would divide $N - p_{1} \dots p_{n} = 1$ , which is impossible.
Thus, $q$ is a new prime not in our list. [cite_start]Contradiction[cite: 89, 90]. ∎

We can prove there are infinitely many primes of specific forms using similar logic.

Suppose there are finitely many:

p_{1}, \dots, p_{n}

. Consider

N = 4 (p_{1} \dots p_{n}) - 1 = 4 K + 3

$N$ must have prime factors.
Not all prime factors can be of the form $4 k + 1$ (since the product of such numbers is $4 k + 1$ ).
Thus, at least one prime factor must be of form $4 k + 3$ .

Note

This simple modification does not work easily for primes of form

4 k + 1

(requires quadratic residues).

Exercise (Problem 1)

Prove there are infinitely many primes of the form

6 k + 5

Exercise (Problem 2)

Prove that for any integer

n > 1

, there is a prime

p

such that

n < p < n! + 2

Exercise (Problem 3)

Show that there are arbitrarily large gaps between consecutive primes. (Hint: Consider the sequence $n! + 2, n! + 3, \dots, n! + n$ ).