# Euclid's proof for the existence of infinitely many prime

The proof goes like this

Suppose to the contrary there exists a list of finite primes which shall be denoted $$\left.\text{\{}p_1,p_2\text{,. . . }p_n\right\}$$ The product of all primes in this list shall be $$\left.\text{P=\{}p_1p_{2. . .}p_n\right\}$$ Now suppose then that $P+1 = q$.

There now exists 2 possibilities:

Case 1: q is a prime. If q itself is a prime number then it is self-implied that there exists a prime number outside the list of finite primes. The claim then that there exists only a finite number of primes is false. Thus, there exists infinitely many primes.

Case 2: If q is not a prime, then the prime factorisation of q is some integer and a prime number $$p_i$$. If $p_i$ is in the list of finite primes then it can be deduced to divide P since P is the product of all finite primes in the list. (My understanding ends here and the confusions begins hence fourth) And I quote Wiki: "But $$p_i$$ divides $q$, divides $p$ and $q$ and the difference between $p$ and $q$. Since no prime number divides 1, this would be a contradiction and so $p$ cannot be on the list. This (what does "this" refers to?) means that at least one more prime number exists beyond those in the list"

*Need some tidying up on the paragraph

• $p_i$ divides both $q$ (by definition of $p_i$) and $P$ (because we have assumed that $p_i$ is one of the factors making up $P$), so it divides $q-P$, which is equal to $1$. But there isn't a prime number that divides $1$. This contradicts our assumption (that $p_i$ is a factor of $P$), so the assumption must be false. So $p_i$ must be a new prime number we didn't already have in our list. – Billy May 2 '15 at 2:55
• I see why now. Thank you – Mathematicing May 2 '15 at 3:24
• Case 1 is redundant since it can be handled in Case 2, which uses only that $\,P+1\,$ is $>1$ so it has a prime factor (possibly itself). Euclid's original proof was constructive, not by contradiction. – Bill Dubuque May 2 '15 at 4:14

If those are all the primes then you can conclude that at least one of them divides 1 which is a contradiction. So you can assume the finite list is not all the primes. Thus there must be infinitely many. But this does not imply $p_1p_2\cdots p_n+1$ is prime for the first $n$ primes. It would only be prime if $p_1,\dots,p_n$ were all the primes.

• Is it necessarily true that if some prime divides a and b then it must divide the difference between a and b? – Mathematicing May 2 '15 at 2:59
• Yes this is true for any number, not just prime. If $k \mid a$ and $k \mid b$ then $k \mid xa + yb$ for any integers $x,y$ and so in particular. $k \mid a - b$ and $k \mid a + b$ – alkabary May 2 '15 at 3:06