Mauro Bringolf

Currently geeking out as WordPress developer at WebKinder and student of computer science at ETH.

There are infinitely many prime numbers and false proofs

January 15, 2017
, ,

Computer science uses a lot of prime numbers so it would be a shame if there were only finitely many. Jokes aside, there are two reasons why I write this post. I recently came across a false version of Euclid’s proof and was once more reminded of how easy it is to fool yourself in a proof. And I wanted to play around with MathJax 1, a JavaScript library that enables LateX on the web.

Euclid’s theorem

So what did the ancient greek Euclid prove? He showed that there are infinitely many prime numbers. This is equivalent to saying there is no largest prime number. This might not surprise you, but it is a fundamental non-trivial fact of number theory. Prime numbers start off quite dense, four of the first 10 numbers are prime numbers. But as the numbers grow, the density of prime numbers decreases and there are different approximations to the rate at which this is happening 2. But although there are less and less prime numbers as they grow, Euclid in ancient greece was able to proof they never end. His proof starts like this:

Take any finite set of prime numbers \( p_1, \dots, p_n \) and consider the number \( m := \prod_{i=1}^n p_i + 1 \). Now all of the prime numbers \( p_i \) divide \( m – 1 \) and therefore none of them divide \(m\).

The goal is to show that there exists a prime number that was not listed in the finite set, i.e. find a prime number \( q \not \in \{ p_1, \dots, p_n \} \). This is the mathematical version of saying there is always one more, which means there are infinitely many. Because when we find such a number, then the same is true for the new finite set \( q, p_1, \dots, p_n \) which means there is another one and so on. And in finding this \( q \) is where the correct and false version of this proof differ:

False: Because none of the prime numbers \(p_1, \dots, p_n \) divide \(m\) it cannot have any proper divisors and therefore is a prime number.

Correct: The number \(m\) can be factored into primes and therefore has at least one prime divisor \(q\). Because none of the numbers \(p_1, \dots, p_n \) divides \( m \) it follows that \( q \not \in \{ p_1, \dots, p_n \} \).

Okay, maybe the proof is just incomplete and m is prime? Without further arguments this is still possible. But you can write a simple program that computes a bunch of these numbers and performs a prime check on them. It turns out that \(m\) is not necessarily prime, there are many counterexamples:

&(2 * 3 * 5 * 7 * 11 * 13) + 1 \\ &= 30031 \\&= 59 * 509

In this case \( 59 \) and \( 509 \) are both prime and would be possible values for a prime number \( q \) that was not listed in \( \{ 2,3,5,7,11,13 \} \).

Displaying math on the web is easy

… but understanding it is still hard. False proofs can look pretty correct. In correct proofs multiple deduction steps might be combined into one at a time, but they can always be refined into a more detailed sequence of implications that can be verified on a lower level. To me that is the most important lesson math has to teach and the reason why I think studying it is rewarding even if you are never going to use it. It shows you how to remove magic by asking more questions and digging deeper. I think this is the mindset you need to successfully learn anything, especially programming.