Infinite Primes proof with possible error

The first link assumes that $p_1,p_2,\cdots,p_n$ are all the primes and then arrives at a contradiction.

If you notice in your example, the prime divisors of $30031$ are different from $2,3,5,7,13$. If these were all the primes then $30031$ would have been a prime number.


The proof as presented by L. Shorser is technically correct but you have to read the whole thing and resist the urge to jump to conclusions. It could certainly be explained better, and with a more natural flow.

Let us assume that there are finitely many primes and label them $p_1, \ldots, p_n$.

For the sake of argument, we're assuming there are only $n$ primes. So far so good. This number $n$ may be 0, but it's definitely not a negative number. Let's say it's a positive integer. Then $$P = 1 + \prod_{i = 1}^n p_i.$$ Clearly $P \equiv 1 \pmod{p_i}$ for any $0 < i \leq n$. That's an obvious consequence of how we defined $P$. At this point, we're still operating under the assumption that there are finitely many primes.

At this point it doesn't seem terribly important to me whether $P$ is prime or not. If $P$ is prime then our value of $n$ was wrong, but a list of $n + 1$ primes is still a finite list of primes. We have more work to do in order to disprove finiteness.

But I got a little ahead of Shorser when I said $n$ ought to be a positive integer.

Since $2$ is a prime number, the list of $p_i$'s is non-empty.

That is, $n > 0$, which confirms $P \neq 1$. Furthermore, if all the $p_i$ are positive, we can also assert that $P > p_i$ for any applicable $i$.

The paragraph with the halmos seems elegant, and is definitely concise, but lots of people get confused by elegant and concise. The assumption that there are finitely many primes is refuted and dismissed in that last paragraph, which means it was still in effect when $P$ was said to be prime.

For what it's worth, I prefer to explain Euclid's proof in a more verbose, less elegant way. Hopefully what my explanation lacks in concise elegance is offset by clarity.

If the $p_i$ really are all the primes that exist, then $P$ must be composite and it must be divisible by at least one of the $p_i$. So either $P$ must be a prime we were previously unaware of, or it must be the product of two or more primes we were unaware of.

Then what we can do with that prime or those primes is append them to our finite list of primes, increment $n$ accordingly and start the process all over again. That will lead us to find at least one more prime that we were unaware of.

Which means that no matter how many primes we know, we can always find primes we didn't know. Therefore the full list of primes is infinite.

I choose to see Euclid's proof as providing a dynamic method by which we can always find more primes, rather than a static object that just sits there.

Let's say you know 2 and 7 are prime but you don't know any other primes. Then $P = 2 \times 7 + 1 = 15 = 3 \times 5$. Neither 3 nor 5 is divisible by 2, and they're both smaller than 7. And clearly 5 is not divisible by 4. So 3 and 5 must be prime. Now we know four primes: 2, 3, 5, 7.

It also works with negative primes, provided $n$ is positive. Suppose $n = 1$ and $p_1 = -29$. Then $P = -28 = -2 \times 2 \times 7 = 2^2 \times -7$. This is no way whatsoever contradicts the fundamental theorem of arithmetic, since both 1 and $-1$ are units, but it does show why it's more convenient to stick to positive primes.

And what if you don't know any primes at all? Then $n = 0$ and $P = 1$. But 1 is not a prime number. There are many reasons for that, some much better than others, and some just plain dumb.

But up until just a couple of centuries ago, 1 was erroneously considered a prime number. What if we use $n = 1$ and $p_1 = 1$? Then $P = 2$, which is indisputably prime. Since now we know that 2 is prime, we can safely remove 1 from the list of primes. Or we can keep in there, the performance penalty is so small as to be of no concern to us.

Then, by continuing the process, we get $2\times3\times7\times43+1 = 1807 = 13 \times 139$, etc.


Yes, the first proof is correct. It applies the following theorem: $P > 1$ is prime if it has no smaller prime divisor. By hypothesis, $\,p_1,\ldots,p_n\,$ are all the primes, and none divide $\,P = 1+p_1\cdots p_n\,$ so the theorem implies that $P$ is prime, contra hypothesis, since $P > p_i \,\Rightarrow\, P\neq p_i$

Note carefully that the deduction that $P$ is prime depends on the hypothesis that there are only finitely many primes. So while it is true that $P$ is prime in the hypothetical theory of the "naturals with finitely many primes", $P$ need not be prime in the real naturals (as your example confirms).

In contradictory theories (such as the naturals with finitely many primes) there are many paths to contradictions. Some may look strange at first glance, esp. in intimately familiar theories like integer arithmetic, where the intermediary inferences are often contrary to well-honed intuition.