3 ms·
Yes, I meant to say "given a purported list of all of the primes".
by not2b 4y ago
Yes, I meant to say "given a purported list of all of the primes".
- cperciva 4y agoEuclid's proof constructs a number which is not a multiple of the purported primes, but it does not construct a new prime.
- not2b 4y agoIt 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.
- a1369209993 4y agoThat'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.
- mcphage 4y agoBecause the list you start with isn't actually a list of all the primes, the number it comes up with isn't necessarily prime.