Infinitude of prime numbers: Euclid, Euler and the mathematical beauty

Euclid with his students

   

Euclid, as depicted above, used to love teaching and sharing his knowledge with others, and made this teaching process one of his daily routines. One day, a youth who had just begun to learn geometry with Euclid, when he had learnt the first proposition, inquired, "What do I get by learning these things?" So Euclid called a slave and said "Give him three pence, since he must make a gain out of what he learns." 

Euclid's answer probably summarizes why there are still people today, who are really not earning a lot , engaging in pure mathematics and spending their lifetime on a subject which will only be understood by a small portion of the human population on earth. Euclid, who is generally referred as the "Father of Geometry" was probably one of the scientists who enjoyed what he was doing the most. Therefore, it probably comes as no surprise that , he established one of the most elegant proofs in the math history- if not the most elegant one.

Euclid's proof

Are prime numbers infinite? Perhaps one of the most interesting things about the infinitude of prime numbers is that, nobody who is not interested in mathematics very much seemed to have a correct/reasonable answer about it. I usually get answers like "Hmmm,I don't know" from people when I asked about this. We can confidently say that the answer for this question is not intuitive, that is to say, it is not related with our everyday experiences nor observations.

When Euclid asked himself this question, and sought for an answer, he found out that the answer was very simple. A summary can be seen below.

Suppose that p₁=2 < p₂ = 3 < ... < p_r are all of the primes. Let P = p₁p₂...p_r+1 and let p be a prime dividing P; then p can not be any of p₁, p₂, ..., p_r, otherwise p would divide the difference P-p₁p₂...p_r=1, which is impossible. So this prime p is still another prime, and p₁, p₂, ..., p_r would not be all of the primes.

Roughly speaking, as you might have already understood, suppose that the number of prime numbers are finite, and let the last prime number be p_r   .So now if you multiplied all the prime numbers including p_r  and just add 1 to it, you would get another prime number, which contradicts with the first assumption. Hence, prime numbers are infinite.

Not only me, but also lots of mathematicians agree that this is one of the most elegant and beautiful proofs in the math history. The fact that it is so simple and can even be understood by a primary school student makes you want to think : "That's it!".

Euler's proof

Leonhard Euler depicted on a 1983 stamp from the German Democratic Republic. The stamp also includes a diagram of an icosahedron and Euler's famous polyhedral formula 

The underlying idea of Euler's proof is very different than that of Euclid's. In fact,although more complicated,his proof is stronger and makes use of analytical methods. In essence, he proves that the sum of the reciprocals of the primes is infinite.  I can't say I am a big fan of Euler because of his intrigues against Daniel Bernoulli, which he conducted with Daniel's father. But anyways, you know what they say: “Render unto Caesar the things which are Caesar’s”.

 

He used the following equality between the regular harmonic series and the infinite products called "Euler products". In the right hand side, p refers to the prime numbers.Euler noted that if there were only a finite number of primes, then the product on the right would clearly converge, contradicting the divergence of the harmonic series. This is a direct result of the fundamental theorem of arithmetic. If you are not convinced, please see: "On the infinitude of prime numbers" by Shailesh A Shirali pg. 9-11.

                                    

Then, Euler took the natural logarithm of both sides and by using the properties of logarithm function he found:

                  

Since

we get e^x > 1 + x and x > ln(1 + x).

So;

Hence diverges. (Because we know the left side diverges as it is equal to the natural logarithm of the sum of the  harmonic series.)But 1/(p_i − 1) < 1/p_i−1 where p_i is the i^th prime. Hence diverges.

This directly implies that , there are infinite number of prime numbers(otherwise the sum would converge).Perhaps none of you could guess a simple divergence test, which you probably learned in Calculus courses, would be the main element of such a beautiful proof.

Mathematical Beauty

Mathematicians usually describe a proof as elegant, when it is simple,unusually succinct, derives a result in a surprising way,is based on new and original insights and can be easily generalized to solve a family of similar problems. Probably one of the main requirements the mathematicians are defending to understand the mathematical beauty is that ,well, "you have to be a mathematician".
 

In his book, "Art of Mathematics", Jerry King draws a figure as depicted above to summarize the  aesthetic view of different people about mathematics.The people in the inner circle (like myself)are people very close to mathematics because they use it day by day, are the ES types (the engineers and scientists). Most engineers and scientists appreciate mathematics solely and only because of its utility. 

The point outside the two concentric circles, point P, represents people who don't care about mathematics. (including most non-science and non-math teachers) These “P people” are unfortunately in the majority.

And according to King, you could only see the beauty of mathematics if you are in the gray zone. That is, if you are a mathematician :) Well a bit arrogant, but who can oppose it ?