The Infinitude of Primes

We now show that there are infinitely many primes. There are several ways to prove this result. An alternative proof to the one presented here is given as an exercise. The proof we will provide was presented by Euclid in his book the Elements.

Theorem 1. There are infinitely many primes.

Proof. We present the proof by contradiction. Suppose there are finitely many primes $p_1$, $p_2$, ..., $p_n$, where n is a positive integer. Consider the integer Q such that $Q = p_1p_2...p_n + 1$. By before Lemma 1, $Q$ has at least a prime divisor, say $q$. If we prove that q is not one of the primes listed then we obtain a contradiction. Suppose now that $q = p_i$ for $1 \le i \le n$. Thus $q$ divides $p_1p_2...p_n$ and as a result $q$ divides $Q - p_1p_2...p_n$. Therefore $q$ divides 1. But this is impossible since there is no prime that divides 1 and as a result q is not one of the primes listed. The following theorem discusses the large gaps between primes. It simply states that there are arbitrary large gaps in the series of primes and that the primes are spaced irregularly.

Theorem 2. Given any positive integer n, there exists n consecutive composite integers.

Proof. Consider the sequence of integers $(n + 1)! + 2$, $(n + 1)! + 3$, ..., $(n + 1)! + n$, $(n + 1)! + n + 1$

Notice that every integer in the above sequence is composite because k divides $(n + 1)! + k$ if $2 \le k \le n + 1 $ by 4.