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

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.

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.

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.