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.