The infinitude of primes and their distribution

Primes thin out as you go further. Do they ever stop? Euclid answered more than two thousand years ago.

There are infinitely many

Euclid's theorem. The set of prime numbers is infinite.

The proof is one of the most elegant in mathematics. It proceeds by contradiction:

1. Suppose there were only FINITELY many primes: p1, p2, ..., pk.

2. Form N = (p1 × p2 × ... × pk) + 1

3. N is larger than every pi, so N is not prime (by assumption).
   It therefore has a prime divisor p, which is in our list.

4. But p divides the product p1 × ... × pk, and p divides N.
   So p divides their difference, which is 1.

5. No prime divides 1.  CONTRADICTION.

The initial assumption is therefore false: there are infinitely many primes.

A point often misunderstood: N is not necessarily prime. For instance 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30,031 = 59 × 509. The proof does not claim N is prime, but that its prime divisor escapes the list.

They thin out

interval             number of primes
----------------     ----------------
1 to 100                    25
101 to 200                  21
1,001 to 1,100              16
10,001 to 10,100            11
1,000,001 to 1,000,100       6

The prime number theorem, proved in 1896, quantifies this thinning:

                                n
   π(n)  ≈  ----------          where π(n) counts the primes below n
              ln(n)

n = 1,000       ->  estimate 145,     actual 168
n = 1,000,000   ->  estimate 72,382,  actual 78,498

The approximation improves relatively as n grows. Concretely: around a 100-digit number, roughly one integer in 230 is prime. This is what makes generating cryptographic keys possible: draw at random until you hit a prime, and it does not take long.

An irregular distribution

Locally, nothing is regular. Twin primes — two primes differing by 2 — seem never to run out:

(3,5)  (5,7)  (11,13)  (17,19)  (29,31)  (41,43) ...

Enormous ones are known, but nobody has proved there are infinitely many. That is the twin prime conjecture, open for over a century. In 2013 Yitang Zhang proved there are infinitely many pairs of primes differing by at most 70 million; the collective effort that followed brought that bound down to 246 — still far from 2.

Conversely, arbitrarily long deserts exist: the sequence

n! + 2,  n! + 3,  ...,  n! + n

gives n - 1 consecutive composite integers, since n! + k is divisible by k. So there exist stretches of a million consecutive integers containing no prime at all.

Summary

• Euclid: there are infinitely many primes, by contradiction.
• The constructed number N = p1…pk + 1 need not be prime — its divisor escapes the list.
• Primes thin out: π(n) ≈ n / ln(n).
• Around 100 digits, roughly 1 integer in 230 is prime.
• Twins: the conjecture is still open; the best known bound is 246.
• Arbitrarily long deserts exist, via n! + k.