5 ms·
Euclid’s proof is famously not constructive, so it doesn’t directly give us a method for constructing a new prime. But it is. He says that given a list of prim
by not2b 4y ago
Euclid’s proof is famously not constructive, so it doesn’t directly give us a method for constructing a new prime.
But it is. He says that given a list of primes P1, P2, ..., PN, construct (P1 * P2 * ... * PN) + 1, which is a new prime not on the list, so given any finite list we can always construct more primes.
- Brigand 4y agoI think you are missing a step in the proof. That could still be a composite, see here: https://newbedev.com/understanding-euclid-s-proof-that-the-number-of-primes-is-infinite https://newbedev.com/understanding-euclid-s-proof-that-the-n...
- _kst_ 4y agoNo, 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.
- kazinator 4y agoThe product of primes plus one isn't always prime. For example: 3*5 + 1 = 16, not prime. Euclid's argument is that the product of some primes plus one is either prime or not; if it's prime, then it's an example of a prime that is not in the list. If it is not prime, then Euclid argues that the number's prime factors are not in the list. To directly use Euclid's result to find a new prime number, we have to multiply some existing numbers together, add 1, and then factor that number. If it doesn't factor, then it is a new prime; otherwise its factors are new primes. That seems constructive; all of the steps amount to a terminating algorithm that will give us at least one new prime.