A calculus of the absurd

6.4.2 Proof that there are infinitely many primes
  • Example 6.4.2 Prove that there is an infinite number of prime numbers.

Let us assume that there are not infinitely many primes. In that case, we can state that there is an ordered set (i.e. every element in the set is less than the previous element in the set) with a finite number of elements, \(\cbrackets {p_1, p_2, p_3, ..., p_n}\) (where \(p_k\) is the kth prime). If we multiply all the prime numbers together and add one to them, then we end up with a new number \(P := \cbrackets {p_1}\cdot \cbrackets {p_2}\cdot \cbrackets {p_3}\cdot ... \cdot \cbrackets {p_n} + 1\). This number must have a prime factor (as every number does - this is an assumption we make, which can be proved separately), which must be one of \(\cbrackets {p_1, p_2, p_3, ..., p_n}\). This means that this number must divide both \(\cbrackets {p_1}\cdot \cbrackets {p_2}\cdot \cbrackets {p_3}\cdot ... \cdot \cbrackets {p_n}\) and \(P\), so it must also divide the difference (i.e. it must divide \(1\)), however, the smallest prime is \(2\) which does not divide \(1\). Therefore, we have found a number which does not have prime factors (which is impossible!) This means we have found an absurdity, and there must be infinitely many primes.

\(\Box \)