The proof that there are infinitely many prime numbers is a proof by contradiction.

First, we note that there is indeed a prime: namely \(2\). We will also state a lemma: that every number greater than \(1\) has a prime which divides it. (This is the easier half of the Fundamental Theorem of Arithmetic, and the slightly stronger statement that “every number may be written as a product of primes” is proved there.)

Now we can proceed to the meat of the proof. Suppose that there were finitely many prime numbers \(p_1, p_2, \ldots, p_n\). Since we know \(2\) is prime, we know \(2\) appears in that list.

Then consider the number \(P = p_1p_2\ldots p_n + 1\) — that is, the product of all primes plus 1. Since \(2\) appeared in the list, we know \(P \geq 2+1 = 3\), and in particular \(P > 1\).

The number \(P\) can’t be divided by any of the primes in our list, because it’s 1 more than a multiple of them. But there is a prime which divides \(P\), because \(P>1\); we stated this as a lemma. This is immediately a contradiction: \(P\) cannot be divided by any prime, even though all integers greater than \(1\) can be divided by a prime.

Example

There is a common misconception that \(p_1 p_2 \dots p_n+1\) must be prime if \(p_1, \dots, p_n\) are all primes. This isn’t actually the case: if we let \(p_1, \dots, p_6\) be the first six primes \(2,3,5,7,11,13\), then you can check by hand that \(p_1 \dots p_6 + 1 = 30031\); but \(30031 = 59 \times 509\). (These are all somewhat ad-hoc; there is no particular reason I knew that taking the first six primes would give me a composite number at the end.) However, we have discovered a new prime this way (in fact, two new primes!): namely \(59\) and \(509\).

In general, this is a terrible way to discover new primes. The proof tells us that there must be some new prime dividing \(30031\), without telling us anything about what those primes are, or even if there is more than one of them (that is, it doesn’t tell us whether \(30031\) is prime or composite). Without knowing in advance that \(30031\) is equal to \(59 \times 509\), it is in general very difficult to discover those two prime factors. In fact, it’s an open problem whether or not prime factorisation is “easy” in the specific technical sense of there being a polynomial-time algorithm to do it, though most people believe that prime factorisation is “hard” in this sense.