Six Ways to Prove that there are Infinitely Many Prime Numbers
How mathematicians come at problems from different angles
One of the first things most mathematics undergraduates learn (and maybe even some smart and enthusiastic high school students) is a proof that there are infinitely many primes. In most cases the proof taught is the classic one developed by the Greek mathematician Euclid around 300BC and presented in Book 9 of his 13-volume Elements treatise.
Unsurprisingly, given that over 2000 years have passed since Euclid published his proof, people have found other approaches to proving that there are infinitely many primes. Some of these are clever ways of restating Euclid’s approach, and some make use of new branches of mathematics which weren’t in existence in Euclid’s time.
Here, for your mathematics pleasure, are six ways of proving that there are infinitely many primes. We will start with Euclid’s classic proof, and move through the others in order of how far removed they are from Euclid’s original approach.
1. Euclid (c. 300BC): For any finite list of primes, there is at least one prime not in that list
First we need a simple supporting result:
Lemma 1.1: For any three integers a, b and c, if a divides b and a divides c then a divides b﹣c.
Proof: b =am for some integer m and c = an for some integer n. Therefore b﹣c = am﹣an = a(m﹣n). Since m﹣n is clearly an integer, a divides b﹣c.
This is all we need for Euclid’s beautiful proof.
Theorem 1.2: If 𝓟 is a finite list of primes, there exists a prime which is not in 𝓟.
Proof: Construct the number P as the product of all the primes in the list 𝓟 and consider the number P+1. If P+1 is prime, we have proven Theorem 1.2. So assume P+1 is not prime. Then P+1 is divisible by some lesser prime p. If p is in our list 𝓟, then p divides both P+1 and P. By Lemma 1.1 p must then also divide P+1﹣ P, so p divides 1. Since this is not possible, p cannot be in our list 𝓟.
2. Hermite (c. 1860): For any positive integer, a larger prime exists
This proof by the French mathematician Charles Hermite is perhaps just as simple as Euclid’s approach.
Theorem 2.1: For any integer n > 1, if p is a prime divisor of n! + 1 then p > n. Hence there are infinitely many primes.
Proof: If p ≤ n, then p divides n!. But p also divides n! + 1, so by Lemma 1.1, p divides n! + 1﹣n!. So p divides 1, which cannot be true. So p > n.
3. Goldbach (1730): There are infinitely many primes because there are infinitely many Fermat numbers
Fermat numbers are numbers of the form
The first 4 Fermat numbers are 3, 5, 17, 257 and then they get pretty big pretty quickly.
First we need an interesting result about Fermat numbers:
Lemma 3.1: For any positive integer m
Proof (by induction):
Now we can prove that any pair of Fermat numbers are coprime, meaning that they do not have any common prime factors.
Lemma 3.2: Any pair of Fermat numbers are coprime.
Proof: Take two Fermat numbers Fᵤ < Fᵥ. If they both had a common prime factor p then by Lemma 3.1 p would divide Fᵥ and Fᵥ ﹣2. Therefore by Lemma 1.1 p would divide Fᵥ﹣(Fᵥ ﹣2), so p would divide 2. But since Fermat primes are clearly odd numbers, this cannot be true, and so both numbers must be coprime.
This now allows an easy proof of the main result.
Theorem 3.3: There are infinitely many primes.
Proof: There are infinitely many Fermat numbers and each of these have different prime factors, so there are infinitely many primes.
As an interesting sidenote, Goldbach’s conjecture about primes is one of the simplest conjectures in number theory that remains unsolved — it states that any even number greater than 2 can be expressed as the sum of two primes.
4. Filip Saidak (2005): You can construct an infinite set of numbers, each of which contains a new prime factor.
This is a very pretty proof which follows easily from some of our earlier results.
First, one of the facts inherent in Euclid’s proof is that, for any positive integer n > 1, n and n + 1 are coprime.
Theorem 4.1: There are infinitely many primes.
Proof: Let n be a positive integer greater than 1. Since n and n+1 are coprime then n(n+1) must have at least two distinct prime factors. Similarly, n(n+1) and n(n+1) + 1 are coprime, so n(n+1)(n(n+1) + 1) must contain at least three distinct prime factors. This can be extended infinitely.
5. Lagrange (c 1800): If there were finitely many primes, Lagrange’s theorem would be contradicted.
From here onwards the proofs require some knowledge of undergraduate Pure Mathematics.
Lagrange established the following important theorem in the field of group theory, the proof of which can be found here.
Theorem 5.1 (Lagrange’s Theorem): The order (cardinality) of any subgroup of a finite multiplicative group G must divide the order of G.
Before we proceed, a quick reminder of the Galois Field GF[p].
Definition 5.2: For a prime p, GF[p] is the finite field of integers modulo p. If we remove the 0 element from GF[p] we form a multiplicative group GF[p]* of order p﹣1. For an element q of GF[p]*, the order of the subgroup generated by q is the smallest value of k such that qᵏ ≡ 1 modulo p.
Example 5.3: GF[5]* is a multiplicative group containing the elements 1, 2, 3, 4. The order of 3 is 4 since 3⁴= 81 ≡ 1 modulo 5.
Theorem 5.4: There are infinitely many primes.
Proof: Assume there are finitely many primes. Let p be the largest prime and consider the number 2ᵖ ﹣1. Let q be a prime that divides 2ᵖ ﹣1. Then 2ᵖ ≡ 1 modulo q. Since p is prime, this means that the element 2 has order p in the group GF[q]*. So GF[q]* has a subgroup of order p. But the order of GF[q]* is q﹣1, so by Theorem 5.1 p must divide q﹣1. So p < q which contradicts our assumption.
6. Furstenberg (1955): If there were finitely many primes, an impossible topology could be constructed
This one is by far the most removed from the others, and probably the most difficult to grasp if you’ve never studied topology, but it is a fascinating look at how topology can help us with algebraic and number-theoretic problems.
Let’s define a topology on the integers as follows:
Definition 6.1: A subset U is an open set if and only if it is the empty set or it is a union of sets of the form S(a, b) where S(a, b) is an arithmetic progression of the form an + b for all integers n and for a ≠ 0.
Example 6.2: All integers is an open set in this topology because it takes the form S(1, 0). The arithmetic progression {…, -4, -1, 2, 5, …} is an open set in this topology because it takes the form S(3, 2).
It can be easily demonstrated that this construction is a valid topology as it satisfies the three axioms: the empty set and the set of all integers are open, any union of open sets is open, and any finite intersection of open sets is open.
Theorem 6.3: There are infinitely many primes.
Proof: Consider the topology defined above. Note that:
- In any topology, the complement of an open set is a closed set. In this topology, a finite non-empty set cannot be open because no S(a, b) is finite. Alternatively stated, in this topology the complement of a finite non-empty set cannot be closed.
- The sets S(a, b) are open by definition, but they can also be written as the complement of open sets as follows, and therefore they are both open and closed (clopen sets):
Now, since all integers except -1 and 1 are the products of primes, we can conclude that they must be in a set S(p, 0) for some prime p, therefore:
The set on the left is the complement of the finite set {-1, 1}, and by point 1 it cannot be closed. Now, if there were finitely many primes, the right hand side would be a finite union of closed sets (by point 2) and therefore would be closed. This leads to a contradiction so there must be infinitely many primes.
Which is your favourite proof, or do you know others? Feel free to comment.