Hacker News Reader

Comment by hiq | Hacker News Reader

[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_pr...

View on HN

Then 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?

Nitpicking 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.

You 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.

All 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.

The product of the first n primes + 1 is not always prime, though. See https://en.m.wikipedia.org/wiki/Euclid_number

  2*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.

I 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

Reply on news.ycombinator.com