Waste less time on Facebook — follow Brilliant.

Really neat proof of the infinitude of primes! Why didn't I think of it?

Here is a really neat proof of the infinitude of primes! It's so simple that it makes me say: "Why didn't I think of it?". In fact, it was made just in 2005, by Filip Saidak, and I was really surprised to know that. So here is the proof:

Let \(n > 1\) be a positive integer. Since \(n\) and \(n+1\) are consecutive integers, they must be coprime, and hence the number \(N_2 = n(n + 1)\) must have at least two different prime factors. Similarly, since the integers \(n(n+1)\) and \(n(n+1)+1\) are consecutive, and therefore coprime, the number \(N_3 = n(n + 1)[n(n + 1) + 1]\) must have at least 3 different prime factors. This can be continued indefinitely.

Note by حكيم الفيلسوف الضائع
3 years, 4 months ago

No vote yet
1 vote


Sort by:

Top Newest

That's really nice!!!

Darn I have to come up with something like that. :P

Nathan Ramesh - 3 years, 4 months ago

Log in to reply

A different proof also exists for the almost same result and with the same concept , apparently.

The proof goes as -

Let us suppose that there are some finite primes \(n\) , suppose. Let the primes be \(a_{1} , a_{2} , \ldots , a_{n}\) such that \(a_{1} = 2 , a_{2} = 3\) and so on. We can clearly conclude that any number is product of some powers of different primes , for example , \(12 = 2^{2} \times 3\). This would mean that every number after \(a_{n}\) is a multiple of different powers of different primes or any number \(y = a_{1}^{x_{1}} \times a_{2}^{x_{2}} \ldots\) where \(x_{1} \) or \(x_{z}\) could be any whole number. But here we try to bring contradiction , suppose there exists a number \(b\) as it would surely exist as numbers are infinite , where \(b=a_{1} \times a_{2} \times a_{3} \ldots a_{n} + 1\). Here , now \(a_{1}, \ldots , a_{n}\) would not be divide \(b\) but leave a remainder of 1 . This contradicts our hypothesis and hence, we are forced to conclude that primes are infinite

Why didn't I think of it !

Utkarsh Dwivedi - 3 years ago

Log in to reply

Thas' a cool rearrangement o' what we learn in school....

Satvik Golechha - 3 years, 3 months ago

Log in to reply

It seems that the proof shown is for infinitude of composite numbers. I fail to see how it shows that there are infinite number of primes,using this proof??

Janardhanan Sivaramakrishnan - 2 years, 4 months ago

Log in to reply

if continued indefinitely, the proof is saying that there is a never ending list of composite numbers with a never ending list of unique prime factors. It is different than a proof by contradiction of a largest prime, and is more like a proof of an infinite number of prime factors

James Brady - 2 years, 1 month ago

Log in to reply

2^prime-1= prime..That means there r infinite prime no.s

Raj kishore Agrawal - 1 year, 6 months ago

Log in to reply

\(2^p-1\) is not always prime for \(p\) being prime. Eg : \(2^{11}-1=2047=23 \times 89\). So, your statement does not actually prove infinite number of primes.

Janardhanan Sivaramakrishnan - 1 year, 6 months ago

Log in to reply

Euclid proves the same by induction over 2000 years ago

Sam Reeve - 1 year, 9 months ago

Log in to reply

Isn't it proof by contradiction ?

Arthur Conmy - 2 months ago

Log in to reply


Neehal Hussain - 2 years, 7 months ago

Log in to reply


Mohamed Khalid - 3 years ago

Log in to reply


Snehal Shekatkar - 3 years ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...