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

  • $\begingroup$ $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. $\endgroup$ – Billy May 2 '15 at 2:55
  • $\begingroup$ I see why now. Thank you $\endgroup$ – Mathematicing May 2 '15 at 3:24
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Is it necessarily true that if some prime divides a and b then it must divide the difference between a and b? $\endgroup$ – Mathematicing May 2 '15 at 2:59
  • $\begingroup$ 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$ $\endgroup$ – alkabary May 2 '15 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.