It is well known that there are infinitely many primes. The proof by Euclid is among the first we see as rising mathematicians. Though it is often put into a proof by contradiction context, the original proof does not actually contain a reducto ad absurdum argument. Below we will share Euclid’s famous proof and a more recent proof by Filip Saidak, a professor at the University of North Carolina at Greensboro.
Recall that a number is prime if the only divisors of are itself and 1. Furthermore, the Fundamental Theorem of Arithmetic (FTA) guarantees that every integer can be factored into primes. Finally if two numbers are coprime then they have no prime factors in common. We begin with Euclid’s proof.
Euclid’s proof: Suppose is a finite set of primes. Consider the number . Since consecutive numbers are coprime, and have no prime factors in common. But FTA guarantees that we can factor into primes. But these primes cannot be in our list. Thus we may add a prime to our list. Since this can be done with any arbitrary number of primes, there must be infinitely many.
Saidak’s proof: Let be a positive integer. Since and are consecutive integers, they must be coprime, and hence the number must have at least two different prime factors. Similarly, the integers and are consecutive, and therefore coprime, the number must have at least 3 different prime factors. This can be continued indefinitely.
Both of these proofs are quite elegant. There are many more proofs of this theorem which I encourage the interested reader to check out in “Proofs from the BOOK”.