The infinitude of prime numbers—Euclid’s proof in my own words

Euclid is believed to be the first mathematician to prove that there are infinitely many prime numbers. Most of us learn only that Euclid established and codified the framework of two- and three-dimensional geometry, but he accomplished far more than that. I think middle-schoolers and high-schoolers are given the impression that Elements was merely a book about the rules and characteristics of geometric shapes, angles, and relationships, but it contained important theorems about number theory, arithmetic, and algebra as well. He was a superb number-theorist and second only to Archimedes among mathematicians of antiquity.

In contradiction with his pigeonholing by school students as a mere geometer, Euclid’s most famous and perhaps most important individual contribution to mathematics is his proof that there are infinitely many prime numbers. This proof also appears in Elements. In my non-scientific experience browsing math websites and blags, Euclid’s proof of the infinitude of primes is almost universally considered one of the most beautiful, elegant (they love that word) proofs in the history of mathematics.

When I read the proof at Wikipedia, I understood it pretty well after reading it a few times, but I found that several months later, I couldn’t remember it or restate it. So I sought out a few more versions of his proof and found a couple that explained it even better. Now I know it for good because I understand it even better than I did the first time—naturally, I understand it best when stated in my own words—and I’ll publish it here for anyone who might be helped by seeing my version:

First, remember that every integer greater than 1 has a unique prime factorization, i.e., it can be written as a unique combination (product) of prime numbers or is prime itself. This is called the fundamental theorem of arithmetic and was also first proved by Euclid. For instance, 12 is factored as 2 x 2 x 3, and 36 is factored as 2 x 2 x 3 x 3. (These examples make it clear that the number of repetitions of each prime is part of the uniqueness, though their order doesn’t matter.)

Now to the meat of the proof. It is basically a proof by contradiction: assume the conjecture (“there are infinitely many prime numbers”) is false, and see that it cannot actually be false. So assume there are finitely many primes, or that you have gone reeeeeaalllllly far out along the number line and have reached the last prime number. Now multiply all of the prime numbers together. Call their product N. Obviously N is not prime because it has a prime factorization: all of the prime numbers. (As a side note, observe that N must be even because it has 2 as a factor. In fact, you know its last digit is 0 because it is divisible by both 5 and 2.)

Add 1 to N to get a new number, N + 1. There are exactly two possibilities for the type of number that N + 1 is: it is either prime or composite. If it is prime, then our assumption was false, because this prime is larger than the supposed largest prime.

If N + 1 is composite, then it has a unique prime factorization. What is that factorization? Well, we don’t know what it is, but we know what it isn’t: it does not include any of the prime factors of N. This is because N + 1 would give a remainder of 1 if divided by any one of the primes, or any combination of the primes, that produced N—by the nature of addition and multiplication, you would have to add 2 to N to get a number that is even divisible by the lowest prime, 2. And you would have to add 3 to get the next number divisible by 3, add 5 to get the next number divisible by 5, etc. Since N is exactly divisible by any and all combinations of those primes, N + 1 would give a remainder of 1 (as opposed to some other remainder) when divided by any combination of them. This means N + 1 is not divisible by any prime factor of N. Therefore, composite N + 1 has some prime factor that was not included in the factors of N, so the supposed list of all primes missed at least one.

This process can be repeated ad infinitum for any N and N + 1 and their prime factors, meaning any finite list of primes cannot include them all, so there are infinitely many primes.

This entry was posted in Math, Theorems. Bookmark the permalink.

Comments are closed.