Infinitude of Primes

Theorem

There are infinitely many prime numbers.

Proof: Suppose instead that there are only finitely many prime numbers, say, \(n\) of them. Let’s call them \(p_1,p_2,p_3,…,p_{n-1},p_n\). Define the new integer \(Q_n\) by multiplying all these primes together, then adding \(1\), i.e.
$$Q_n=p_1\cdot p_2\cdot p_3\cdot…\cdot p_{n-1}\cdot p_n+1.$$
We claim that the above number \(Q_n\) is not divisible by any one of our finitely many primes above. To prove this, we will suppose that one of our primes \(p_1,…,p_n\) divides \(Q_n\), and show why that can’t work (that is, produce what is called a contradiction).

We know that every natural number has a prime divisor (if the number is prime, then that divisor is itself), so let \(q\) be a prime divisor of \(Q_n\). Now, if \(q\) is one of the primes listed above, then \(q\) divides both \(Q_n\) and the product \((p_1\cdot p_2\cdot p_3\cdot…\cdot p_{n-1}\cdot p_n)\). Thus, if we subtract that product from both sides of the above equation, we have
$$Q_n-(p_1\cdot p_2\cdot p_3\cdot…\cdot p_{n-1}\cdot p_n)=1.$$
Note that since \(q\) divides both \(Q_n\) and \((p_1\cdot p_2\cdot p_3\cdot…\cdot p_{n-1}\cdot p_n)\), it follows that \(q\) divides the difference, i.e. the left-hand side of the equation just above. Since \(q\) divides the left-hand-side, \(q\) also divides the right-hand-side because the two sides are equal. But this can’t happen since \(q\) is prime; primes can’t divide \(1\). Therefore, \(q\) can’t be one of the primes \(p_1,…,p_n\), implying that there need to be more primes than what are in that list. This contradicts the initial assumption that there are only finitely many (i.e. \(n\)) primes. Therefore, there can’t be only finitely many primes.