Infinitude of Primes

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 p>1 is prime if the only divisors of p 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 \{p_1,p_2,...,p_n\} is a finite set of primes. Consider the number n = p_1\cdot p_2\cdot...\cdot p_n. Since consecutive numbers are coprime, n and n+1 have no prime factors in common. But FTA guarantees that we can factor n+1 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 n>1 be a positive integer. Since n and n+1 are consecutive integers, they must be coprime, and hence the number N_2 = n(n+1) must have at least two different prime factors. Similarly, the integers n(n+1) and n(n+1)+1 are consecutive, and therefore coprime, the number N_3 = n(n+1)[n(n+1)+1] 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”.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s