Response to a Developer about Euclid’s proof


This post is a response to some doubts about Euclid’s proof of prime numbers from “Notes of a Developer “.

So, before you even start reading this you may want to take a look at this post:

Bringof’s approach on how Euclid’s proof might be incomplete is a really good observation. Especially, at some point, he wrote that there is a correct and a false version which are, according to him:


It follows a numerical example in order to explain his statement and correction:


However, the false is the correct one, and the correct is false.


The numerical example shows that the number 30031 is not prime, that’s true. The above-mentioned example would prove wrong the following statement: “Every number of the form p1*p2*p3*…*pn + 1 is a prime number, where { p1, p2, p3,…,pn } are prime numbers “. It is not what Euclid said.

Euclid said that:

Let suppose that there is a finite set of prime numbers and let that be { p1, p2, p3,…,pn}. That means that in a perfect world those are the only prime numbers. There are no others. He continued his constructive proof by saying that there is a number m that m=p1*p2*p3*…*pn + 1.

But none of the prime numbers we know can divide m. With the assumption he made, that means that m is a prime number itself and doesn’t belong to the set of the prime numbers which is Contradiction!

Do we care if m is actually a prime or not? No, because with our assumption it is a prime number.

Going back to the numerical example the assumption is that: the only prime numbers that exist are { 2, 3, 5, 7, 11, 13 }, none of these numbers can divide 30031, that makes 30031 a prime number which doesn’t belong to the set of the prime number, contradiction!

With the assumption we made we don’t actually know that 59 or 509 are prime numbers. {2, 3, 5, 7, 11, 13} are the only prime numbers that exist according to the assumption we made.

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