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 𝓟.
