3 ms·

> 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 s

> 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

> 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.