5 ms·

It is constructive, because it relies on the fact that p_1p_2...p_n + 1 has a prime factor, and to prove this you repeatedly split it into factors until you rea

It is constructive, because it relies on the fact that p_1p_2...p_n + 1 has a prime factor, and to prove this you repeatedly split it into factors until you reach a prime. And so when you consider all the parts of the proof you find that you have in fact constructed another prime.

thaumasiotes 11y ago
I don't understand what you're saying. You don't prove that p_1p_2...p_n + 1 has a prime factor (how would you do that?) -- you postulate it. The proof is done as soon as you observe that the number you've constructed must have a prime factor greater than p_n. It's not necessary to construct the prime factor, although I guess it's possible to do so.
- ColinWright 11y ago
  There are several things you've said here that would worry me if said by an undergrad. You must have a new prime because the number you construct has a prime decomposition, and that prime decomposition cannot use any of the prunes you started with. And your collection so far need not contain all primes so far, so the new prime need not be bigger than the ones you already have, so you can not, as you claim, observe that the number you've constructed must have a prime factor greater than p_n. It may be that you were just being informal, but statements like this coming from an undergrad would make me start to investigate how secure their knowledge really is.
  - thaumasiotes 11y ago
    Here's the proof I learned: 1. Assume there is no prime number larger than p_n. 2. Compute the product of all the prime numbers less than or equal to p_n, plus one. Call this number c. 3. By construction, no prime number less than or equal to p_n divides c. 4. But all integers greater than one have one or more prime factors. (This is not proven.) 5. Therefore, since c has no prime factors less than or equal to p_n, it must have one which is not less than or equal to p_n, or in other words c must have a prime factor greater than p_n, which contradicts step (1). Viewing https://en.wikipedia.org/wiki/Euclid%27s_theorem https://en.wikipedia.org/wiki/Euclid%27s_theorem, I see that Euclid's original proof doesn't involve using all the primes within a certain range ("your collection so far need not contain all primes so far"), so what you've said here does apply to it. However, I also read: > Euclid is often erroneously reported to have proved this result by contradiction, beginning with the assumption that the set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes. So I don't feel too bad about referring to the proof I gave above as "the famous proof". I didn't call it "the proof that appears in Euclid's Elements". Since this result is by contradiction, there are several different points where you could choose to observe the contradiction. But you can certainly do it before you actually produce a new prime.
    - ColinWright 11y ago
      In step 1 you haven't assumed that you know all the primes up to p_n, and then in step 2, you assume that you do have them. If you don't make step 1 more precise, saying that you know all the primes up to p_n, then when you multiply them all together and add 1, step 3 fails. The point is that the proof is fairly robust, and yet stating it all completely correctly is actually quite hard. Here is a more correct version: We know there are at least some primes. For example, 3 is prime. Take any non-empty finite collection of primes. Multiply them all together, and add 1. The result may not be prime, but it is expressible as the product of primes, and hence there is at least one prime that divides it. That prime cannot be one of the primes in our finite collection, and hence any finite collection of primes does not contain them all. The classic counter-examples used when there are proof with holes are these: Consider the set of primes { 3, 5 }. Multiply them together and add 1, and all the primes that divide the result are less than the primes you have. Starting with 2 and then repeatedly getting a new prime by multipying and adding 1 we get 3, then 7, then 43, but 2.3.7.43+1 = 13.139. Finally, taking known successive primes we get "failure" at: 2.3.5.7.11.13+1 = 59.509 And as an addendum, I've heard this before, but a few days ago Carl Pomerance told me of a joke he heard from Henrik Lenstra. Here's a proof that there are infinitely many composites: 4 is composite, 6 is composite. Suppose by way of contradiction that the set of all composites is finite. Multiply them all together and don't add 1! That's a new composite, hence contradiction. QED.
      - thaumasiotes 11y ago
        > In step 1 you haven't assumed that you know all the primes up to p_n, and then in step 2, you assume that you do have them. If you don't make step 1 more precise, saying that you know all the primes up to p_n, then when you multiply them all together and add 1, step 3 fails. Why? We know that the largest prime is p_n, and the numbers from 1 to p_n are finite. Each of them might or might not be prime. It's perfectly legitimate to say "multiply together all the primes between 1 and p_n" without knowing which numbers in particular those happen to be. Since I don't know which numbers I multiplied together, I won't know the numeric value of the number produced in step 3, but I certainly do know that by construction, it is not divisible by any prime <= p_n. (Technically, I know this conditional on the lemma "all prime numbers are greater than one.) The proof I've given doesn't deal with arbitrary sets of primes at all. There is no point in the proof at which you could multiply 3 and 5 and then add one to produce 16. If 5 is the largest prime, the number (implicitly) computed in step 3 is 2⋅3⋅5 + 1 = 31. Iterating from 2 (but why?), you'd compute 3, then 7, then 211, and then something large. And 2⋅3⋅5⋅7⋅11⋅13 + 1 = 30031 = 59⋅509 isn't a counterexample to the proof I've given, because the conclusion is explicitly "the number constructed must have a prime factor greater than p_n", and p_n in this example is 13. 59 and 509 are both greater than 13. Where does my proof fail? How is yours more correct? You still seem to think that I'm misstating the proof found in the Elements. You can prove things more than one way.

thaumasiotes 11y ago

I don't understand what you're saying. You don't prove that p_1p_2...p_n + 1 has a prime factor (how would you do that?) -- you postulate it. The proof is done as soon as you observe that the number you've constructed must have a prime factor greater than p_n. It's not necessary to construct the prime factor, although I guess it's possible to do so.

ColinWright 11y ago
There are several things you've said here that would worry me if said by an undergrad. You must have a new prime because the number you construct has a prime decomposition, and that prime decomposition cannot use any of the prunes you started with. And your collection so far need not contain all primes so far, so the new prime need not be bigger than the ones you already have, so you can not, as you claim, observe that the number you've constructed must have a prime factor greater than p_n. It may be that you were just being informal, but statements like this coming from an undergrad would make me start to investigate how secure their knowledge really is.
- thaumasiotes 11y ago
  Here's the proof I learned: 1. Assume there is no prime number larger than p_n. 2. Compute the product of all the prime numbers less than or equal to p_n, plus one. Call this number c. 3. By construction, no prime number less than or equal to p_n divides c. 4. But all integers greater than one have one or more prime factors. (This is not proven.) 5. Therefore, since c has no prime factors less than or equal to p_n, it must have one which is not less than or equal to p_n, or in other words c must have a prime factor greater than p_n, which contradicts step (1). Viewing https://en.wikipedia.org/wiki/Euclid%27s_theorem https://en.wikipedia.org/wiki/Euclid%27s_theorem, I see that Euclid's original proof doesn't involve using all the primes within a certain range ("your collection so far need not contain all primes so far"), so what you've said here does apply to it. However, I also read: > Euclid is often erroneously reported to have proved this result by contradiction, beginning with the assumption that the set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes. So I don't feel too bad about referring to the proof I gave above as "the famous proof". I didn't call it "the proof that appears in Euclid's Elements". Since this result is by contradiction, there are several different points where you could choose to observe the contradiction. But you can certainly do it before you actually produce a new prime.
  - ColinWright 11y ago
    In step 1 you haven't assumed that you know all the primes up to p_n, and then in step 2, you assume that you do have them. If you don't make step 1 more precise, saying that you know all the primes up to p_n, then when you multiply them all together and add 1, step 3 fails. The point is that the proof is fairly robust, and yet stating it all completely correctly is actually quite hard. Here is a more correct version: We know there are at least some primes. For example, 3 is prime. Take any non-empty finite collection of primes. Multiply them all together, and add 1. The result may not be prime, but it is expressible as the product of primes, and hence there is at least one prime that divides it. That prime cannot be one of the primes in our finite collection, and hence any finite collection of primes does not contain them all. The classic counter-examples used when there are proof with holes are these: Consider the set of primes { 3, 5 }. Multiply them together and add 1, and all the primes that divide the result are less than the primes you have. Starting with 2 and then repeatedly getting a new prime by multipying and adding 1 we get 3, then 7, then 43, but 2.3.7.43+1 = 13.139. Finally, taking known successive primes we get "failure" at: 2.3.5.7.11.13+1 = 59.509 And as an addendum, I've heard this before, but a few days ago Carl Pomerance told me of a joke he heard from Henrik Lenstra. Here's a proof that there are infinitely many composites: 4 is composite, 6 is composite. Suppose by way of contradiction that the set of all composites is finite. Multiply them all together and don't add 1! That's a new composite, hence contradiction. QED.
    - thaumasiotes 11y ago
      > In step 1 you haven't assumed that you know all the primes up to p_n, and then in step 2, you assume that you do have them. If you don't make step 1 more precise, saying that you know all the primes up to p_n, then when you multiply them all together and add 1, step 3 fails. Why? We know that the largest prime is p_n, and the numbers from 1 to p_n are finite. Each of them might or might not be prime. It's perfectly legitimate to say "multiply together all the primes between 1 and p_n" without knowing which numbers in particular those happen to be. Since I don't know which numbers I multiplied together, I won't know the numeric value of the number produced in step 3, but I certainly do know that by construction, it is not divisible by any prime <= p_n. (Technically, I know this conditional on the lemma "all prime numbers are greater than one.) The proof I've given doesn't deal with arbitrary sets of primes at all. There is no point in the proof at which you could multiply 3 and 5 and then add one to produce 16. If 5 is the largest prime, the number (implicitly) computed in step 3 is 2⋅3⋅5 + 1 = 31. Iterating from 2 (but why?), you'd compute 3, then 7, then 211, and then something large. And 2⋅3⋅5⋅7⋅11⋅13 + 1 = 30031 = 59⋅509 isn't a counterexample to the proof I've given, because the conclusion is explicitly "the number constructed must have a prime factor greater than p_n", and p_n in this example is 13. 59 and 509 are both greater than 13. Where does my proof fail? How is yours more correct? You still seem to think that I'm misstating the proof found in the Elements. You can prove things more than one way.