Hacker News Reader

Comment by paulddraper | Hacker News Reader

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.

View on HN

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