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