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 $\scriptstyle {\mathcal {S}}$ of primes, compute their product

$N=\prod _{p\in {\mathcal {S}}}p.\,$

It is obvious that $\scriptstyle N+1\,$ is not divisible by any of the primes that exist, the remainder being 1 in all cases. So either $\scriptstyle N+1\,$ is prime or is a composite with its prime factors not on the set $\scriptstyle {\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 $\scriptstyle \mathbb {P} \,$ the set of all prime numbers. Since 2 is prime, $\scriptstyle \mathbb {P} \,$ is not the empty set. We will now demonstrate that there is no finite subset $\scriptstyle Q\,$ of $\scriptstyle \mathbb {P} \,$ which exhausts $\scriptstyle \mathbb {P} \,$. Let's designate the elements of the non-empty subset $\scriptstyle Q\,$ as $\scriptstyle q_{1},\ldots ,q_{\mathrm {len} }\,$ then compute $\scriptstyle m\,=\,1+\prod _{i=1}^{\mathrm {len} }q_{i}\,$. The "fundamental theorem of arithmetic" implies there is a prime $\scriptstyle p\,$ which divides $\scriptstyle m\,$. Since no $\scriptstyle q_{i}\,$ divides $\scriptstyle m\,$, it follows that $\scriptstyle p\,\notin \,Q\,$ and $\scriptstyle Q\,\neq \,\mathbb {P} \,$. Therefore, $\scriptstyle \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 $\scriptstyle {\mathcal {S}}\,$ is simply the set of all primes no bigger than the largest one in $\scriptstyle {\mathcal {S}}$, and call that one $\scriptstyle p_{\max }\,$. With $\scriptstyle p_{\max }\,=\,5\,$, we have $\scriptstyle N\,=\,30\,$

and $\scriptstyle N+1\,=\,31\,$, which is prime, and much larger than 5. We could work out on the number line an example in which $\scriptstyle N+1\,$ is composite (with a prime factor greater than $\scriptstyle p_{\max }\,$) but the dots for the prime factors of $\scriptstyle N\,$ would be crowded too close together to be useful as an illustration.

The numbers $\scriptstyle N+1\,$ for $\scriptstyle \max \,=\,0\,$ forward are sometimes called the "Euclid numbers" (see A006862.) The numbers $\scriptstyle 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 $\scriptstyle 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 $\scriptstyle 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 $\scriptstyle a_{n+1}\,$ is the smallest prime factor (for A005265) or largest prime factor (for A005266) of $\scriptstyle 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.

References

• H. Davenport, The Higher Arithmetic, 6th Ed. Cambridge University Press (1992): pp. 17–18.
• Benjamin Fine and Gerhard Rosenberger, Number Theory: An Introduction via the Distribution of Primes, Boston: Birkhäuser (2007) pp. 16–17, Theorem 2.3.1.
• Thomas Koshy, Elementary Number Theory with Applications, Harcourt Academic Press (2002): p. 100, Theorem 2.10.
• Paulo Ribenboim, The Little Book of Bigger Primes, Second Edition. New York: Springer Verlag (2004) p. 3.
• Michael Hardy and Catherine Woodgold, "Prime simplicity," The Mathematical Intelligencer, 31:4, pp. 44–52.