# Proof that there are infinitely many primes

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.

Parents:

• Prime number

The prime numbers are the “building blocks” of the counting numbers.

• How does this prove that P isn’t divisible by any non-prime number? This could be clearer.