4 ms·
[nitpicking] This version of Euclid's proof does not look like the one on Wikipedia, which is not a proof by contradiction. The article[0] mentions that: "Euc
by hiq 10y ago
[nitpicking]
This version of Euclid's proof does not look like the one on Wikipedia, which is not a proof by contradiction. The article[0] mentions that:
"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."
[/nitpicking]
[0]: https://en.wikipedia.org/wiki/Euclid's_theorem#Euclid.27s_proof https://en.wikipedia.org/wiki/Euclid's_theorem#Euclid.27s_pr...
- paulddraper 10y agoNitpicking indeed. Euclid's proof: Every finite set of primes {p1,p2,...pn} has a prime, namely p1p2...pn + 1, not in the set. Contradiction proof: The hypothetical finite set of all primes {p1,p2,...pn} would have a prime, namely p1p2...pn + 1, not in the set. I'd hardly call the latter a different proof.
- tprice7 10y agoYou made an error: p1p2...pn + 1 is not necessarily prime, but none of its prime factors are in {p1, ..., pn}. For example, 15 = 2 * 7 + 1 is not prime, but neither 3 nor 5 are in {2, 7}. I agree with your overall point though.
- daveguy 10y agoAll primes. Not just the primes you choose. The set of the first n primes here would be {2,3,5,7}. The product plus 1 is 235*7+1 = 211 is prime.
- pmiller2 10y agoThe product of the first n primes + 1 is not always prime, though. See https://en.m.wikipedia.org/wiki/Euclid_number https://en.m.wikipedia.org/wiki/Euclid_number
- deleted 10y ago[deleted]
- yen223 10y ago2*3*5*7*11*13 + 1 = 30031 = 59*509 Neither 59 nor 509 is in {2, 3, 5, 7, 11, 13}, so the proof still holds, but the resultant number is not a "prime" number.
- hiq 10y agoI said it was nitpicking because it is only remotely relevant to the article, but the distinction does matter in mathematics. See for instance this post[0], where this very proof is discussed in the comments. [0]: http://math.stackexchange.com/a/1688 http://math.stackexchange.com/a/1688
- thethirdone 10y agoThen Euclid's proof does not show that there are infinitely many primes (as is commonly reported). It is trivial to show that there are infinitely many primes from it though through proof by contradiction as follows: 1. Assume there are finitely many primes. 2. Write a list of all the primes. (Writing a list of finite elements is possible) 3. There exists a prime not in that list (By Euclid's proof) 4. All primes are in the list. 3 and 4 contradict and therefore the single assumption is incorrect. So there are infinitely many primes. As a sidenote, it seems that proving there are infinitely elements of any set will need to be proven by contradiction. Is there any proof of that?