×

# 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, 2 months ago

Sort by:

That's really nice!!!

Darn I have to come up with something like that. :P · 3 years, 1 month ago

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 ! · 2 years, 9 months ago

Thas' a cool rearrangement o' what we learn in school.... · 3 years ago

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?? · 2 years, 1 month ago

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 · 1 year, 10 months ago

2^prime-1= prime..That means there r infinite prime no.s · 1 year, 3 months ago

$$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. · 1 year, 3 months ago

Euclid proves the same by induction over 2000 years ago · 1 year, 6 months ago

dang · 2 years, 4 months ago

really · 2 years, 9 months ago