3 ms·
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,
by _kst_ 4y ago
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.)
- not2b 4y agoYes, 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.
- dpbriggs 4y agoIt'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.
- _kst_ 4y agoApparently 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.