# Proof that there are infinitely many primes

The proof that there are in­finitely many prime num­bers is a proof by con­tra­dic­tion.

First, we note that there is in­deed a prime: namely $$2$$. We will also state a lemma: that ev­ery num­ber greater than $$1$$ has a prime which di­vides it. (This is the eas­ier half of the Fun­da­men­tal The­o­rem of Arith­metic, and the slightly stronger state­ment that “ev­ery num­ber may be writ­ten as a product of primes” is proved there.)

Now we can pro­ceed to the meat of the proof. Sup­pose that there were finitely many prime num­bers $$p_1, p_2, \ldots, p_n$$. Since we know $$2$$ is prime, we know $$2$$ ap­pears in that list.

Then con­sider the num­ber $$P = p_1p_2\ldots p_n + 1$$ — that is, the product of all primes plus 1. Since $$2$$ ap­peared in the list, we know $$P \geq 2+1 = 3$$, and in par­tic­u­lar $$P > 1$$.

The num­ber $$P$$ can’t be di­vided by any of the primes in our list, be­cause it’s 1 more than a mul­ti­ple of them. But there is a prime which di­vides $$P$$, be­cause $$P>1$$; we stated this as a lemma. This is im­me­di­ately a con­tra­dic­tion: $$P$$ can­not be di­vided by any prime, even though all in­te­gers greater than $$1$$ can be di­vided by a prime.

# Example

There is a com­mon mis­con­cep­tion that $$p_1 p_2 \dots p_n+1$$ must be prime if $$p_1, \dots, p_n$$ are all primes. This isn’t ac­tu­ally 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$$. (Th­ese are all some­what ad-hoc; there is no par­tic­u­lar rea­son I knew that tak­ing the first six primes would give me a com­pos­ite num­ber at the end.) How­ever, we have dis­cov­ered a new prime this way (in fact, two new primes!): namely $$59$$ and $$509$$.

In gen­eral, this is a ter­rible way to dis­cover new primes. The proof tells us that there must be some new prime di­vid­ing $$30031$$, with­out tel­ling us any­thing 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 com­pos­ite). Without know­ing in ad­vance that $$30031$$ is equal to $$59 \times 509$$, it is in gen­eral very difficult to dis­cover those two prime fac­tors. In fact, it’s an open prob­lem whether or not prime fac­tori­sa­tion is “easy” in the spe­cific tech­ni­cal sense of there be­ing a polyno­mial-time al­gorithm to do it, though most peo­ple be­lieve that prime fac­tori­sa­tion is “hard” in this sense.

Parents:

• Prime number

The prime num­bers are the “build­ing blocks” of the count­ing num­bers.

• How does this prove that P isn’t di­visi­ble by any non-prime num­ber? This could be clearer.