The point of adding $1$ in Euclid's proof of infinitely many primes I am interested in understand the proof of infinitely many primes. It seems like quite an easy proof, ( I know there are many but I am referring to the proof that goes as follows);
" Suppose there are only finitely many primes, lets say n of them, we can denote them as p1,p2,..,pn. Now we construct a new number P=(p1)(p2)..(pn)+1. Clearly P is larger than any of the primes, so it does not equal any one of them. Since p1,p2,,pn constitute all primes, P cannot be a prime. Thus it must be divisible by at least one of our finitely many primes, say pn. But when we divide P by Pn we get a remainder of 1 which is a contradiction. So our original assumption must be false."
I understand a lot of what it is saying, I am just not understanding where the +1 ties in. I see that if we assume P is not prime, and then cannot divide without a remainder there is a contradiction, but what if that +1 was not in the statement question originally?
I hope what I am asking makes sense to you guys,
Thanks a lot.
(Source for proof Hans Riesel, Prime Numbers and Computer Methods for Factorization, Birkhaeuser, 1985, ISBN 0-8176-3291-3.)
 A: The key idea is that we can generate an integer coprime to any finite set of integers by taking their product, then adding $\,{\bf\color{#c00}1}.\,$ Therefore, iterating this method  we can generate an infinite sequence $\ 2,\,3,\,7,43,\ \ldots,\,$ via $\ \color{#0a0}{f_{n}} = \,\color{#c00}{\bf 1} + f_1\cdots f_{n-1}$ of coprimes, i.e. $\,{\rm gcd}(f_n,f_k) = 1\,$ if $\,n>k,$ by any common divisor of $\,\color{#0a0}{f_n},\,\color{#c0e}{f_k}\,$ divides
$\, \color{#c00}{\bf 1} = \color{#0a0}{f_n} - f_1\cdots \color{#c0e}{f_k}\cdots f_{n-1}.$
Any infinite sequence $\,f_n > 1 \,$ of coprimes  yields an infinite sequence of distinct primes $\, p_n $ obtained by choosing $\,p_n$ to be any prime factor of $\,f_n,\,$ e.g. the least factor $> 1.$
Remark $ $ A shorter variant of Euclid's proof arises by noting that iterating the map $\, n\mapsto n^2\!+n$ generates integers with an unbounded number of prime factors, because $\,n(n+1)\,$ includes all prime factors of $\,n\,$  plus some (new!) prime factor of $\,n+1,\,$ since $\,n\,$ and $\,n+1\,$ are coprime.
A: If the +1 were not there, then P would be composite, and we wouldn't know whether there was another prime beyond pn. This way, we're guaranteed that there is one:
With the +1, either


*

*P is composite, the product of primes other than the pi in the list (since it's definitely not divisible by any prime in the list) - contradicting our assumption about the pi; or

*P is itself a prime; but it's not in the list - again a contradiction.


Without the +1, P is definitely composite, and the product of primes in the list - which doesn't let us conclude anything about primes that may not be in the list.
A: An almost identical question was posted here in recent hours.  Here is the answer I posted.

This proof by contradiction is a badly organized proof.  It should instead be done like this:
Suppose you have any finite set of primes $p_1,\ldots,p_n$.  (DO NOT assume that there are no other primes.)
Then no prime factor of $(p_1\cdots p_n)+1$ can be one of the primes $p_1,\ldots,p_n$. (That part you can prove by contradiction without, as far as I know, introducing flaw into the proof that would not otherwise be there.)
Therefore there is at least one more prime than $p_1,\ldots,p_n$.  No matter how many you've listed so far, there is at least one more. ${}\qquad\blacksquare$
That is how Euclid did it.
One of the problems of rearranging this into the frequently seen proof by contradiction is just that that adds an extra complication to the proof that serves no purpose, thereby making the proof appear more complicated than it really is.
Another problem is this: Some authors (e.g. G. H. Hardy (not related to me as far as I know)) say something along these lines: Because $(p_1\cdots p_n)+1$ is not divisible by any of the primes, it must itself be prime, and then we get a contradiction.  Only the assumption that the list $p_1,\ldots,p_n$ contains all primes --- an assumption that is present only when this is rearranged into a proof by contradiction --- causes anyone to say that it is not divisible by any primes, and only that conclusion makes anyone say that therefore it is itself prime.  This leads students to think mistakenly that it has been proved that if you multiply the first $n$ primes and then add $1$, the number you get is always prime.  But that is false.  And if a student then finds counterexamples (e.g. the six smallest primes) then the student may mistakenly conclude that the proof is simply wrong.
Another problem with preseting it as a proof by contradiction is that authors who do that often explicitly state that Euclid did it that way.  That is historically false.
Catherine Woodgold and I wrote a joint paper, published in the Mathematical Intelligencer in fall 2009, debunking the false historical claims and demonstrating the superiority of Euclid's version over the proof by contradiction falsely attributed to Euclid.
And you shouldn't say "infinite primes" when you mean "infinitely many primes".  "Infinite primes" would be primes each one of which is infinite.  In colloquial speech the word "infinite" may be used that way, but in mathematical terminology it is an incorrect usage.

