Understanding Euclid's proof that the number of primes is infinite.

Question

In Euclid's proof, if $p_1, p_2, \dots, p_n$ are the only primes then $p_1 \times p_2 \times \dots \times p_n + 1$ is not divisible by any of $p_1, p_2, \dots, p_n$ (because of some algebraic facts), which makes another prime and is a contradiction.

The proof makes sense logically, and I tried some numerical examples to "feel" the proof better but...

$2 \times 3 \times 5\times 7\times 11\times 13+1$ is not a prime! $2 \times 3 \times 5\times 7\times 11\times 13 \times 17+1$ is also not prime! Why is the general case proof is not working for these examples?

Answer 1

Suppose there are finitely many primes. Then we can enumerate them as a set $$P = \{p_1, p_2, \ldots, p_n\}.$$ The number $m = p_1 p_2 \ldots p_n + 1$ is either prime or composite. If it is prime, then we have found a prime that is not among the finite set $\{p_1, \ldots, p_n\}$ of primes we assumed to comprise the collection of all primes. If it is composite, then it is divisible by a prime. But it cannot be divisible by any of $p_1, p_2, \ldots, p_n$, for upon dividing $m$ by any of these primes, it leaves a remainder of $1$. Therefore, $m$ is divisible by a prime that again is not in the presumed set of all primes. In either case, a contradiction is obtained in which the assumption that there are finitely many primes is violated.

Answer 2

$2\times3\times5\times7\times11\times13+1$ does not need to be prime, all it says in the proof is that this number is not divisible by any of the primes used to create it, namely 2,3,5,7,11 and 13. The fact that this number needs to be divisible by some prime then yields the result that the list of primes is not complete

Answer 3

Euclid's proof was not by contradiction. Many respectable authors say it was, and they're wrong. Dirichlet may have been the originator of the error.

Euclid said that if you take any finite set $S$ of primes (which need not be the first $n$ primes) then the prime factors of $1+\prod S$ are not members of $S$; hence there is at least one more prime than those in any finite set $S$.

Say the finite set you start with is $S=\{5,7\}$. Then $1+\prod S = 36 = 2\times2\times3\times3$, so the additional prime numbers are $2$ and $3$.

There's nothing in that that says $1+\prod S$ (which in the example above is $36$) is prime. That comes up only when the proof is rearranged into a proof by contradiction, and then $1+\prod S$ is shown to be prime, not in the actual sequence of natural numbers, but in the hypothetical set of all natural numbers that contains only finitely many primes. Since that hypothetical set is ultimately shown not to exist, there's no problem.

Moral of the story: Rearranging this into a proof by contradiction makes the matter confusing and more complicated --- hence in those ways inferior to Euclid's original proof.

PS: By popular demand (expressed in comments below), here is a proof that $1+\prod S$ is not divisible by any of the members of $S.$ Suppose $p$ is one of the members of $S.$ If you divide $\prod S$ by $p,$ the quotient is the product of all the other members of $S$ and the remainder is $0$, so if you divide $1+\prod S$ by $p,$ the quotient is the product of those other members and the remainder is $1$. Since the remainder is $1,$ the number $1+\prod S$ is not divisible by $p.$

For example: Suppose $S=\{5,7,13\}.$ Then $N= 1+\prod S$ is $1 + (5\times7\times 13) = 456.$

If you divide $N$ by $5$, the quotient is $7\times 13$ and the remainder is $1.$

If you divide $N$ by $7$, the quotient is $5\times 13$ and the remainder is $1.$

If you divide $N$ by $13$, the quotient is $5\times 7$ and the remainder is $1.$

Dividing $N$ by any of the members of $S$ leaves a remainder of $1$, so $N$ is not divisible by any of those members.

Answer 4

It is a common mistake to think that $p_1p_2...p_n+1$ is prime, it is simply divisible by a prime that is not one of those used in the product.

And to address your comment - if you do get a prime from $p_1...p_n + 1$, it is divisible by a prime not in the list, which just happens to be itself.

Answer 5

The reason that your numerical examples do not work is because the conclusion that "$p_1 p_2 \ldots p_n + 1$ is prime" was based on a false assumption ($p_1, p_2, \ldots, p_n$ are all the primes) made for the purposes of obtaining a contradiction. Once you obtain the contradiction, you've proven the original statement (there are infinitely many primes) but there is no reason to believe any of the intermediate statements will hold, because they are all based on an assumption which you now know to be false.

Answer 6

It depends on how you start. You can start with "assume that $p_1$ to $p_n$ are primes, and I will demonstrate that there is another prime". You take the product of $p_1$ to $p_n$, add 1, and get a number not divisible by any prime $p$ within $p_1$ to $p_n$, so that number is either a prime itself, or divisible by a prime other than those in the set $p_1$ to $p_n$, and in either case we have another prime.

Or you can try a proof by contradiction. You start with "assume that $p_1$ to $p_n$ are all the primes. Then the product plus 1 is not divisible by any prime (because it is divisible by $p_1$ to $p_n$, which are all the primes) and therefore it is a prime. On the other hand, since $p_1$ to $p_n$ are all the primes it's even more obviously not a prime :-) So we get a contradiction. So the assumption "$p_1$ to $p_n$ are all the primes" is false.