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

First, we note that there is indeed a prime: namely . 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}, \dots, p_{n}$ . Since we know $2$ is prime, we know $2$ appears in that list.

Then consider the number $P = p_{1} p_{2} \dots 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.

Proof that there are infinitely many primes