Waste less time on Facebook — follow Brilliant.

Euler's proof of the infinitude of primes

Almost all of us are familiar with Euclid's proof regarding the infinitude of primes but in this post I will discuss the way Leonhard Euler approached it.I didn't find this proof on anywhere on Brilliant so I decided to do a post on this.

Leonhard Euler

Leonhard Euler

Image Credit:Wikipedia

\(\textbf{Proof:}\)According to the fundamental theorem of Arithmetic every integer\( n\) can be represented as the product of prime numbers \(n = p_1^{a_1} p_2^{a_2}...... p_k{a_k}\).

Let us assume there are finitely many primes \(p_1<p_2<p_3<......<p_n\).

Let us denote by \(N\) the following product:

\[N = (1 + \frac{1}{p_1}+\frac{1}{p_1^{2}}+\frac{1}{p_1^{3}}+...)(1 + \frac{1}{p_2}+\frac{1}{p_2^{2}}+\frac{1}{p_2^{3}}+..)....\] \[....(1 + \frac{1}{p_n}+\frac{1}{p_n^{2}}+\frac{1}{p_n^{3}}+...)\]

Now for each term in the product we can evaluate the sum of the expression using infinite GP(since \(\frac{1}{p_i}<1\) ) to be : \[ (1 + \frac{1}{p_i}+\frac{1}{p_i^{2}}+\frac{1}{p_i^{3}}+...) = \frac{p_i}{p_i-1}\]

So clearly the expression on the right hand side is finite...so N corresponds to a finite expression. - (1)

But now if we multiply out the terms in n then we will get the sum of the reciprocals of all the natural numbers because every natural number is the product of primes and each distinct combination of primes lead to a natural number.Clearly we can see that the product of the expressions in N leads to the occurrence of every possible combination of the prime numbers in the denominator and hence the reciprocals of all natural numbers . That is

\[N = (1 + \frac{1}{p_1}+\frac{1}{p_1^{2}}+\frac{1}{p_1^{3}}+...)(1 + \frac{1}{p_2}+\frac{1}{p_2^{2}}+\frac{1}{p_2^{3}}+..)....\] \[....(1 + \frac{1}{p_n}+\frac{1}{p_n^{2}}+\frac{1}{p_n^{3}}+...)\]

\[N = 1+\frac{1}{2}+\frac{1}{3}+........\]

We know that this series is diverging which contracts equation 1 which proved the finiteness of N.Hence we have a contradiction!!

So there are infinitely many primes.

\(\textbf{Personal Note:}\)It will be extremely helpful for me if Mr.Calvin Lin and other staff members offer a bit of constructive criticism of my posts and offer some advice on how I can improve my writing skills.My peers are also welcome to do the same..Here are my previous posts:

Partitioning of integers

Fermat's Method of infinite descent

Stacking problems

Note by Eddie The Head
2 years, 8 months ago

No vote yet
1 vote


Sort by:

Top Newest

I like User Submitted posts on Brilliant...I get to learn so many new things! If I may make a suggestion, could you write about methods of finding extremes of a function as one of your next posts? I was wondering what methods exist and had put up a post for the community, but didn't get any satisfactory responses. See https://brilliant.org/discussions/thread/extremes-of-a-function/?ref_id=105581 Rohan Rao · 2 years, 8 months ago

Log in to reply

@Rohan Rao Do you mean finding the maxima and minima using calculus? That's a great idea... actually I was thinking about doing one on Newton' method of approximating roots of a function... Eddie The Head · 2 years, 8 months ago

Log in to reply

@Eddie The Head I meant the various ways by which we can find the extremes, because sometimes, calculus is overkill for a question, but some inequality, say Cauchy Schwarz, makes short work of it. So I wanted a sort of guideline as to which technique to choose when. Rohan Rao · 2 years, 8 months ago

Log in to reply

@Rohan Rao Maybe we can start a new thread for that where many people will be able to express their approach towards these problems???That would be cool.. Eddie The Head · 2 years, 8 months ago

Log in to reply

@Eddie The Head Yea, that's what I had in mind...but my post didn't garner many comments or any real discussion...I need more re shares. Rohan Rao · 2 years, 8 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...