# Proof that there are infinite prime numbers

We want to show that it is not the case that there only finitely many primes. Suppose there are finitely many primes. We shall show that this assumption leads to a contradiction. Let $p_1,\dots,p_n$ be all the primes there are. Let $x=p_1\cdots p_n$ be their product and let $y=x+1$. Then $y\in\mathbb N$ and $y\ne1$, so there is a prime $q$ such that $q\mid y$. Now $q$ must be one of $p_1,\dots,p_n$ since these are all primes that there are. Hence $q\mid x$. Since $q\mid y$ and $q\mid x$, $q\mid y−x$. But $y-x=1$. Thus $q\mid1$. But since q is prime, $q\ge2$. Hence $q$ does not divide 1. Thus we have reached a contradiction. Hence our assumption that there are only finitely many primes must be wrong. Therefore there must be infinitely many primes.

In this proof, what is the guarantee that there is no prime number say $m$ between $p_n$ and $y$ such that $m\mid y$ ?

• Because $p_n$ is the biggest prime ever, so $m > p_n$ is not prime. – Maffred Feb 5 '18 at 2:14
• I assum you mean $p_n,$ not $pn$. But it's still irrelevant.... $q$ $must$ be one of $p_1,...,p_n$ so $q|x$ and $q|y$ so $q|(y-x)=1.$ – DanielWainfleet Feb 5 '18 at 4:34
• The 1st chapter of the book Prime Number Records gives about 22 different proofs. My favorite, due to Prof. Leo Morse, is that it suffices to exhibit a strictly increasing infinite sequence of pair-wise co-prime natural numbers, e.g. the Fermat numbers $F(n)=1+2^{2^n}$ for $n\in \Bbb N\cup \{0\}.$ (It is easy to show that $\gcd (F(m),F(n))=1$ when $m<n.$) – DanielWainfleet Feb 5 '18 at 4:41
• If you are asking about a proof of the infinitude of primes that is quoted above, please give your Readers the source of this quotation. – hardmath Feb 5 '18 at 5:31

We have assumed that $p_1, \dots, p_n$ is the complete list of primes, and given that this list was written in order, $p_n$ is the greatest prime. So if $m$ is between $p_n$ and $y$, in particular $m > p_n$, so $m$ is not on the list, and since the list is complete, $m$ is not prime (Maffred has already made this point in the comments).
However, you have raised an important point about understanding what inferences we can draw from the proof. After we have rejected our assumption that there are only finitely many primes -- i.e., that $p_1, \dots, p_n$ gives the full list, we might be tempted to say that $y$ gives the next prime. However, we don't necessarily know this -- we know only that there is some prime bigger than $p_n$ which divides $y$. In some cases, $y$ itself is prime: e.g., if we start with the list $2,3,5$, then $y = 2 \cdot 3 \cdot 5 + 1 = 31$ is prime. But if we start with the list $2,3,5,7,11,13$, multiply them and add $1$, we get $30031$, which is not prime, but is divisible by a prime ($59$) larger than $13$ (source).