4 ms·

Good one. You could argue they are defined as infinite though because the proof that there are infinitely many is not hard. If there are finite, multiply them

Good one. You could argue they are defined as infinite though because the proof that there are infinitely many is not hard. If there are finite, multiply them all and add one. This number is prime. QED

lovecg 3y ago
On that topic, this is a very common misconception about how that proof works. Multiplying all the primes and adding one does not have to be a prime (just try 2 x 3 x … x 13 + 1) - the point is it’s not divisible by any of the supposedly finite number of primes, so it must have some other prime divisor.
- quickthrower2 3y ago
  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.

lovecg 3y ago

On that topic, this is a very common misconception about how that proof works. Multiplying all the primes and adding one does not have to be a prime (just try 2 x 3 x … x 13 + 1) - the point is it’s not divisible by any of the supposedly finite number of primes, so it must have some other prime divisor.

quickthrower2 3y ago
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.