4 ms·

Thanks I worded it wrong! You are correct.

im3w1l 3y ago
Your original proof is correct. Yes the number may not actually be prime, but given the assumption that you have finitely many primes it follows that the number you have constructed is prime, since it has no divisors. 2 x 3 x … x 13 + 1 isn't prime but that's because that's just a subset of the primes, not all of them. And the argument relies on using all of them.
- lovecg 3y ago
  This is a confusing way to present this argument. We can’t say, by assumption we used up all the primes, so the new number must be a new prime - this doesn’t make sense. And you might as well say the new number has some new prime divisors (could be the number itself, could be new primes smaller than the number), which is at least slightly more correct. The actual proof is by contradiction, and goes something like this: 1) Let’s assume there’s a finite number of primes 2) Multiply them all and add one 3) Since we assumed 1), the result in 2) must have a divisor that’s one of those finite number of primes 4) But that’s not the case since we always get a remainder of one 3) and 4) is a contradiction, therefore 1 is false. At no point it follows that the number in 2) is a prime. The misconception also often causes people to assume that any first N primes + 1 is a prime itself, which is not correct. Someone will use this to make an insecure cryptographic system eventually :) Just kidding, but you see my point how it’s not just a technical detail.
  - tshaddox 3y ago
    > We can’t say, by assumption we used up all the primes, so the new number must be a new prime - this doesn’t make sense. I'm not sure what you mean. Are you simply pointing out that it's a contradiction? Because, indeed, it is a contradiction, and that's the point. It's a proof by contradiction! The contradiction you state in step 4 is precisely equivalent to the contradiction "the new number must be a new prime." Stating "N has non-zero remainder when divided by each prime less than N" is equivalent to stating "N is prime." However this is not equivalent to the statement "any first N primary + 1 is prime" which is indeed a misconception.
    - lovecg 3y ago
      > Stating "N has non-zero remainder when divided by each prime less than N" is equivalent to stating "N is prime." This confuses N, the bound on the largest prime, and the number (call it M) that’s the product of the all primes < N plus one. M is much larger than N. So what you’re really saying is: > Stating "M has non-zero remainder when divided by each prime less than N" is equivalent to stating "M is prime." This makes it clear where the error is, the correct statement should be: > Stating "M has non-zero remainder when divided by each prime less than N" is equivalent to stating "M is either a prime or a product A x B where A is a prime > N”
    - kazinator 3y ago
      The argument isn't that the newly formed integer is a prime! The argument is that the newly formed integer has a divisor which is none of the primes in the original set that was multiplied together. It's not any of those primes, because none of those primes divide it. Therefore that divisor must be a prime which is not in that set, contradicting the assumption that the set is complete. Since the argument works for any finite set of primes, it shows that no finite set of primes can contain all the primes. Thus there are always more primes. There are times when that product + 1 will be that divisor (i.e. that number is prime). Not always though. One such example is if we claim that the only primes which exists are 2, 3 and 5. 2 x 3 x 5 + 1 = 31. 31 is not divisible by 2, 3 or 5, leaving a remainder of 1, so we know it has a divisor that is a prime, and that is not one of those. It so happens that that divisor is 31 itself, since 31 is prime. With some other sets of primes, that won't be the case. An example where the product plus one is not prime is the product of the primes 2 .. 13. That product is 30031, which is a composite number factorizing to 59 and 509. Because 30031 is not divisible by 2, 3, 5, 7, 11 or 13, we know that it has at least one prime factor which isn't any of those. It has two such factors: 59 and 509.
  - im3w1l 3y ago
    A proof by contradiction works by assuming something incorrect, and using it to prove various incorrect things until finally we manage to prove both p and not p for some proposition p. Being able to prove such an absurdity shows that the assumptions must be wrong. In this case we can prove that the constructed number both is prime (it's not divided by ANY prime hence it's prime) and isn't prime (it's not in the list hence it's not prime).
    - lovecg 3y ago
      Ok I see what you’re getting at. Maybe a better way to construct this version of the argument is - every integer > 1 is either a prime or a product of primes (this is easy to show by induction) - assume there’s a finite number of primes - then the product of all primes + 1 must be either a prime or a product of primes - but we know that it’s _neither_ (can’t be divided by any of the primes in the list, and not itself in the list), which is a contradiction - it had to be one or the other.

Your original proof is correct. Yes the number may not actually be prime, but given the assumption that you have finitely many primes it follows that the number you have constructed is prime, since it has no divisors. 2 x 3 x … x 13 + 1 isn't prime but that's because that's just a subset of the primes, not all of them. And the argument relies on using all of them.

lovecg 3y ago
This is a confusing way to present this argument. We can’t say, by assumption we used up all the primes, so the new number must be a new prime - this doesn’t make sense. And you might as well say the new number has some new prime divisors (could be the number itself, could be new primes smaller than the number), which is at least slightly more correct. The actual proof is by contradiction, and goes something like this: 1) Let’s assume there’s a finite number of primes 2) Multiply them all and add one 3) Since we assumed 1), the result in 2) must have a divisor that’s one of those finite number of primes 4) But that’s not the case since we always get a remainder of one 3) and 4) is a contradiction, therefore 1 is false. At no point it follows that the number in 2) is a prime. The misconception also often causes people to assume that any first N primes + 1 is a prime itself, which is not correct. Someone will use this to make an insecure cryptographic system eventually :) Just kidding, but you see my point how it’s not just a technical detail.
- tshaddox 3y ago
  > We can’t say, by assumption we used up all the primes, so the new number must be a new prime - this doesn’t make sense. I'm not sure what you mean. Are you simply pointing out that it's a contradiction? Because, indeed, it is a contradiction, and that's the point. It's a proof by contradiction! The contradiction you state in step 4 is precisely equivalent to the contradiction "the new number must be a new prime." Stating "N has non-zero remainder when divided by each prime less than N" is equivalent to stating "N is prime." However this is not equivalent to the statement "any first N primary + 1 is prime" which is indeed a misconception.
  - lovecg 3y ago
    > Stating "N has non-zero remainder when divided by each prime less than N" is equivalent to stating "N is prime." This confuses N, the bound on the largest prime, and the number (call it M) that’s the product of the all primes < N plus one. M is much larger than N. So what you’re really saying is: > Stating "M has non-zero remainder when divided by each prime less than N" is equivalent to stating "M is prime." This makes it clear where the error is, the correct statement should be: > Stating "M has non-zero remainder when divided by each prime less than N" is equivalent to stating "M is either a prime or a product A x B where A is a prime > N”
  - kazinator 3y ago
    The argument isn't that the newly formed integer is a prime! The argument is that the newly formed integer has a divisor which is none of the primes in the original set that was multiplied together. It's not any of those primes, because none of those primes divide it. Therefore that divisor must be a prime which is not in that set, contradicting the assumption that the set is complete. Since the argument works for any finite set of primes, it shows that no finite set of primes can contain all the primes. Thus there are always more primes. There are times when that product + 1 will be that divisor (i.e. that number is prime). Not always though. One such example is if we claim that the only primes which exists are 2, 3 and 5. 2 x 3 x 5 + 1 = 31. 31 is not divisible by 2, 3 or 5, leaving a remainder of 1, so we know it has a divisor that is a prime, and that is not one of those. It so happens that that divisor is 31 itself, since 31 is prime. With some other sets of primes, that won't be the case. An example where the product plus one is not prime is the product of the primes 2 .. 13. That product is 30031, which is a composite number factorizing to 59 and 509. Because 30031 is not divisible by 2, 3, 5, 7, 11 or 13, we know that it has at least one prime factor which isn't any of those. It has two such factors: 59 and 509.
- im3w1l 3y ago
  A proof by contradiction works by assuming something incorrect, and using it to prove various incorrect things until finally we manage to prove both p and not p for some proposition p. Being able to prove such an absurdity shows that the assumptions must be wrong. In this case we can prove that the constructed number both is prime (it's not divided by ANY prime hence it's prime) and isn't prime (it's not in the list hence it's not prime).
  - lovecg 3y ago
    Ok I see what you’re getting at. Maybe a better way to construct this version of the argument is - every integer > 1 is either a prime or a product of primes (this is easy to show by induction) - assume there’s a finite number of primes - then the product of all primes + 1 must be either a prime or a product of primes - but we know that it’s _neither_ (can’t be divided by any of the primes in the list, and not itself in the list), which is a contradiction - it had to be one or the other.