structural:summarization, structural:expansion
Infinitude of primes

Euclid's theorem states that there are infinitely many primes. In Euclid's Elements the theorem is stated in Book IX, Proposition 20:

Depending on how we formally write the above statement, the usual proof takes either the form of a proof by contradiction or a refutation by contradiction. We present here the former, see below how the proof is done as refutation by contradiction.

If we formally express Euclid's theorem as saying that for every natural number n {\displaystyle n} there is a prime bigger than it, then we employ proof by contradiction, as follows.

Given any number n {\displaystyle n}, we seek to prove that there is a prime larger than n {\displaystyle n}. Suppose to the contrary that no such p exists (an application of proof by contradiction). Then all primes are smaller than or equal to n {\displaystyle n}, and we may form the list p 1, …, p k {\displaystyle p_{1},\ldots,p_{k}} of them all. Let P = p 1 ⋅ … ⋅ p k {\displaystyle P=p_{1}\cdot \ldots \cdot p_{k}} be the product of all primes and Q = P + 1 {\displaystyle Q=P+1}. Because Q {\displaystyle Q} is larger than all prime numbers it is not prime, hence it must be divisible by one of them, say p i {\displaystyle p_{i}}. Now both P {\displaystyle P} and Q {\displaystyle Q} are divisible by p i {\displaystyle p_{i}}, hence so is their difference Q − P = 1 {\displaystyle Q-P=1}, but this cannot be because 1 is not divisible by any primes. Hence we have a contradiction and so there is a prime number bigger than n {\displaystyle n}