The point of adding $1$ in Euclid's proof of infinitely many primes

Question

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.)

Answer 1

The key idea is that we can construct an integer coprime to any finite set of integers by taking their product, then adding $\:\!{\bf\color{#c00}1}.\,$ So iterating this process generates an infinite sequence of (pair) $\rm\color{#0af}{ coprimes}$ $\ 2,\,3,\,7,43,\, \ldots,\,$ via $\ \color{#0a0}{f_{n}} = \,\color{#c00}{\bf 1} + f_1\cdots f_{n-1},\,$ i.e. $\,\color{#0af}{{\rm gcd}(f_n,f_k) = 1}\,$ if $\,n>k\,$ since 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.

Answer 2

If the +1 were not there, then P would be composite, and we wouldn't know whether there was another prime beyond p_n. This way, we're guaranteed that there is one:

With the +1, either

1. P is composite, the product of primes other than the p_i in the list (since it's definitely not divisible by any prime in the list) - contradicting our assumption about the p_i; or
2. 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.