Response to a Developer about Euclid’s proof

ff

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: https://maurobringolf.ch/2017/01/there-are-infinitely-many-prime-numbers-and-false-proofs/.

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:

Capture1

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

Capture2

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

Explanation:

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.

Euclid’s proof of prime numbers

I was 15 when I first learned about this proof. The Mathematician, who was a volunteering math trainer to me, was the one who first introduced that proof to me.

He was talking about that beauty, how in math we can agree with someone “ Okay, let suppose that you are right” and then prove them wrong.

It’s amazing how powerful and beautiful the method of “proof by contradiction” is.

In addition, this proof became my favorite.

19457594_1132605616844814_1224509537_o