This site is supported by donations to The OEIS Foundation.

# Euclid's proof that there are infinitely many primes

After centuries, Euclid's proof of the following theorem remains a classic, not just for proving this particular theorem, but as a proof in general.

Theorem. There are infinitely many primes.

Proof (Euclid). Given a finite set ${\mathcal {S}}$ of primes, compute their product

$N=\prod _{p\in {\mathcal {S}}}p.\,$ It is obvious that $N+1\,$ is not divisible by any of the primes that exist, the remainder being 1 in all cases. So either $N+1\,$ is prime or is a composite with its prime factors not on the set ${\mathcal {S}}$ . Either way, we have at least one new prime. □

This classic proof can be dressed up in many guises. For example:

Proof (Euclid–Bolker) Designate by $\mathbb {P} \,$ the set of all prime numbers. Since 2 is prime, $\mathbb {P} \,$ is not the empty set. We will now demonstrate that there is no finite subset $Q\,$ of $\mathbb {P} \,$ which exhausts $\mathbb {P} \,$ . Let's designate the elements of the non-empty subset $Q\,$ as $q_{1},\ldots ,q_{\mathrm {len} }\,$ then compute $m\,=\,1+\prod _{i=1}^{\mathrm {len} }q_{i}\,$ . The "fundamental theorem of arithmetic" implies there is a prime $p\,$ which divides $m\,$ . Since no $q_{i}\,$ divides $m\,$ , it follows that $p\,\notin \,Q\,$ and $Q\,\neq \,\mathbb {P} \,$ . Therefore, $\mathbb {P} \,$ is infinite.

Of course in this version it is necessary to prove the fundamental theorem of arithmetic first.

Since Euclid viewed numbers primarily as geometric constructs, it is appropriate to work out a couple of examples on the number line. Consider the case in which ${\mathcal {S}}\,$ is simply the set of all primes no bigger than the largest one in ${\mathcal {S}}$ , and call that one $p_{\max }\,$ . With $p_{\max }\,=\,5\,$ , we have $N\,=\,30\,$  and $N+1\,=\,31\,$ , which is prime, and much larger than 5. We could work out on the number line an example in which $N+1\,$ is composite (with a prime factor greater than $p_{\max }\,$ ) but the dots for the prime factors of $N\,$ would be crowded too close together to be useful as an illustration.

The numbers $N+1\,$ for $\max \,=\,0\,$ forward are sometimes called the "Euclid numbers" (see A006862.) The numbers $N\,$ are the primorials; see A002110. The Euclid numbers that are prime are listed in A018239 as "primorial primes." For the smallest prime factor of the $n\,$ th Euclid number, see A051342.

Factorials (A000142) are sometimes used rather than primorials in the proof; their disadvantage is that they grow much faster on account of the many repeated factors (especially 2), though in all fairness, the primorials also quickly grow beyond the range for which a typical calculator can show in full precision.

Euclid's proof even works if in our assumed finite list of primes we skip some of the smaller primes. If we were to say, for example, that 2, 3 and 19 are the only primes, the prime factorization of $N+1\,$ would then reveal a prime we skipped over as well as a prime larger than the prime we declared to be the largest. Euclid's proof suggested the following sequences (A005265 and A005266) to Neil Sloane and other mathematicians, defined by the following recurrence relation:

$a_{1}=3\,$ $b_{n}=\prod _{k=1}^{n}a_{k}\,$ and $a_{n+1}\,$ is the smallest prime factor (for A005265) or largest prime factor (for A005266) of $b_{n-1}\,$ .

## Proving there are infinitely many primes of specific forms

The basic principle of Euclid's proof can be adapted to prove that there are infinitely many primes of specific forms, such as primes of the form $4k+3$ . (Here, as is the case throughout this article, we're dealing only with positive primes, but all conclusions can easily be extended to negative primes).

Theorem 4K3. There are infinitely many primes of the form $4k+3$ .

Proof. Label as $Q$ the set of all primes of the form $4k+3$ . We assert that $Q$ is finite, and that it has $n$ elements, from $q_{1}$ to $q_{n}$ . Compute $m=-1+4\prod _{i=1}^{n}q_{i}$ . Clearly $m>1$ , and also $m\equiv 3\mod 4$ and $\gcd(m,q_{i})=1$ for each $q_{i}\in Q$ . Per the fundamental theorem of arithmetic, $m$ is either a prime or the product of two or more primes. But if $m$ is prime that contradicts our assertion that $Q$ is finite. So, not only is $m$ composite, all of its prime divisors are of the form $4k+1$ . However, since $(4k+1)(4j+1)=16kj+4k+4j+1\equiv 1\mod 4$ , at least one (but possibly three or five or seven, etc.) of $m$ 's prime divisors must be of the form $4k+3$ . Whether $m$ is prime or composite, we have found at least one prime of the form $4k+3$ that is not $Q$ , and if we append that prime to $Q$ , we can derive yet another prime of the form $4k+3$ , and therefore $Q$ is in fact infinite. □

See A002145.