Hacker News Reader

HNHacker News

Top New Best Ask Show Jobs

Comment by _kst_ | Hacker News Reader

Parent Full thread

_kst_·

No, the constructed number (P1 * P2 * ... * PN) + 1 either is prime or has a prime factor greater than PN.

For example, (2 * 3 * 5 * 7 * 11 * 13) + 1 is 30031, which is 59 * 509

(Apparently I misremembered the details of Euclid's proof. See the comments below.)

View on HN

It's not necessarily a prime bigger than PN as the original proof is about some list of primes, not all primes less than some prime. E.g. 3,5 becomes 16, which is missing 2.

Apparently I misremembered the details of the proof.

I thought that it started with (P1, P2, P3, ..., PN) being a list of all the primes from 2 up to PN. Since (P1 * P2 * ... * PN) + 1 either is prime or has a prime factor not in the list, that prime factor must be greater than PN.

Apparently (according to Wikipedia's summary) Euclid started with an arbitrary list of primes, and showed that for any such list there is a prime not in the list.

Either method works to show that there are infinitely many primes.

Yes, I meant to say "given a purported list of all of the primes".

Euclid's proof constructs a number which is not a multiple of the purported primes, but it does not construct a new prime.

It constructs a number that is not divisible by any member of the list, so either it is prime, or there is some other prime that is not a member of the list. Either way we can grow the list.

That's technically true of the exact version of the proof usually presented, but it's a really bad example of a nonconstructive proof, because it can trivially be made constructive by taking the least integer greater than PN that is a factor of (P1*...*PN)+1 as your new prime.

Because the list you start with isn't actually a list of all the primes, the number it comes up with isn't necessarily prime.

Reply on news.ycombinator.com