FTA: “For example, one of the oldest results in math is Euclid’s proof from 300 BCE that there are infinitely many prime numbers. It begins with the recognition that you can always find a new prime by multiplying all known primes and adding 1”
So, if all the primes you know are 5 and 7, you can find a new one by computing 5×7+1? ;-)
This is a very common error. The claim doesn’t even hold if you know the first n primes. The first counterexample is 2×3×5×7×11×13+1=59×509. All you can tell is that the result has at least one prime factor that’s not yet in your list.
Here's a slightly more rigorous version of the proof for anyone interested:
1. Suppose the list of primes is finite, and that they are P_1, P_2, P_3 .., P_n
2. Consider the new number P_1 * P_2 * P_3 * .. * P_n + 1. None of the P_is divide this number. Therefore, by definition, it it is a prime.
3. The number we found in (2) is not any of the P_is, and it is a prime. This contradicts the assumption we made in (1). So, the assumption in (1) is wrong, there must be infinitely many primes
The examples in parent's post do not work because they do not follow the framework of this proof. I see parent's point that the claim in the article isn't technically correct, but I think it's reasonable to allow some handwaving in an accessible article written in English :-)
It's true that's a common error, but if we're going to be really pedantic: the article doesn't say that multiplying all known primes and adding 1 results in a prime number, it says it's a way to find a new prime. (In fact, all of the result's prime factors are primes that weren't in the list you started with.)
Picking a random number isn't guaranteed to help you find a prime number. However, doing the "take all the prime numbers and multiply them and add 1" always produces at least one prime number; either the result or the factors of the number.
I seem to be associated with that quote (and of course I didn't say it -- indeed when I spoke to Quanta I used factorials plus one). When the article appeared I emailed Kevin Hartnett immediately to suggest replacing that line with something like "...using 1 plus the product of all known primes" but he seemed to be happy with what he'd written -- his argument was that what he wrote was ambiguous but not definitely wrong.
So, if all the primes you know are 5 and 7, you can find a new one by computing 5×7+1? ;-)
This is a very common error. The claim doesn’t even hold if you know the first n primes. The first counterexample is 2×3×5×7×11×13+1=59×509. All you can tell is that the result has at least one prime factor that’s not yet in your list.