$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 2.2: The Infinitude of Primes

• • Contributed by Wissam Raji
• Associate Professor and the Chairman (Mathematics) at American University of Beirut
$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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.

There are infinitely many primes.

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 Lemma 3, $$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\leq i\leq 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.

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

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\leq k\leq n+1$$ by [thm4].

Exercises

1. Show that the integer $$Q_n=n!+1$$, where $$n$$ is a positive integer, has a prime divisor greater than $$n$$. Conclude that there are infinitely many primes. Notice that this exercise is another proof of the infinitude of primes.
2. Find the smallest five consecutive composite integers.
3. Find one million consecutive composite integers.
4. Show that there are no prime triplets other than 3,5,7.