Proof there are an infinite number of prime numbers

in mathematics •  2 years ago

Over 2000 years ago Euclid was possibly the first to give a proof that there are an infinite number of primes. A proof of this is actually very simple and fairly easy to understand. It is even often touted as a good example of a proof by contradiction. It goes something like this ~


Suppose there are a finite number of prime numbers. Let's denote them from smallest to largest as

p1, p2, p3, p4, ..., pn

Where p1 is the first prime number (that is 2), p2 is the second and so on, and pn is whatever the last, largest prime number is. We can find another prime number that isn't in this group.


Consider the number
p1 * p2 * p3 * ... * pn + 1

It isn't divisible by any of the prime numbers p1 to pn, making it only divisible by 1 and itself, thus making it a new prime number that wasn't in our list. Meaning it is impossible for there to be a finite number of prime numbers, for we can always find another, proving that there must be an unlimited or infinite number of prime numbers!

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  

I've always loved this proof!

haiku_proof06af0.png

Oh, I remember that day when I was studying Math Induction. And this was one of the first examples)

Steve Patterson destroys the idea that there are infinite sets here: http://steve-patterson.com/cantor-wrong-no-infinite-sets/

·

I started reading it but stop because well it is long and I know where this wasgoing. The author didn't do much of analysis because he would have to "kill himself" from "apparent contradiction overload". I am not saying it is obvious and I am not saying I agree with everything that lie in the border of maths logical. I am just "not impress" by such an article.

·

It's a bit of semantics based on whether concepts can be said to actually exist or not. But mathematicians simply define existence in such a way that they do. I can accept, as in his article on Zeno's Paradox, that there are no physical infinities. I agree with this talk by George Ellis:

My teachers never accepted this demonstration. Their point was (from wikipedia:

Euclid is often erroneously reported to have proved this result by contradiction, beginning with the assumption that the finite set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes.[4] Although the proof as a whole is not by contradiction (it does not assume that only finitely many primes exist), a proof by contradiction is within it, which is that none of the initially considered primes can divide the number q above.

I always thought this was complicated for no special reason so I prefer the one you show. I find more natural.