Infinitude of primes — the series

1. 

   There is no last prime

   Euclid's argument is often described as producing a new prime from any finite list. It does not, and the number it builds is frequently composite — which makes the proof more interesting rather than less.

   part 1 · number
2. 

   Infinitely many of one kind

   Euclid's argument produces a prime nobody had listed, and says nothing about what it looks like. Ask for infinitely many primes ending in 3, or leaving a remainder of 1 on division by 4, and the same construction has to be aimed — and for most targets nobody knows how to aim it.

   part 2 · number
3. 

   Which infinitudes are proved

   The primes never stop, and neither — apparently — do the twin pairs, the primes one more than a square, or the Mersenne primes. Three of those four statements are theorems and one is not, and counting the members of each family tells nobody which.

   part 3 · number
4. 

   Every class, and in equal shares

   Euclid's argument aimed at a residue class reaches some classes and stalls at others. The theorem covering all of them is Dirichlet's, its proof abandons arithmetic entirely for analysis, and what it proves is stronger than infinitude — the classes are equal, though not at any point anybody has counted.

   part 4 · number
5. 

   The sieve that cannot finish

   Sifting out the composites is the oldest method in the subject and it has a ceiling nobody has raised. The reciprocals of the twin primes add to a finite number, so no argument that measures thickness can reach them — and the inclusion–exclusion every sieve truncates goes wildly wrong before it goes right.

   part 5 · number
6. 

   Two halves a sieve cannot tell apart

   Split the whole numbers into those with an even number of prime factors and those with an odd number. To a sieve — which sees only how many numbers each small divisor divides — the two halves look almost exactly alike. Yet sifting out the small primes leaves every prime in one half and nothing at all in the other. That is Atle Selberg's parity example, and it is the reason no sieve can prove there are infinitely many twin primes.

   part 6 · number
7. 

   The patterns primes are allowed to make

   Primes two apart are twin primes; primes six apart are about twice as common; three primes two apart happen exactly once, at 3, 5, 7. Which patterns of primes can recur for ever is decided by remainders alone — a pattern must leave some remainder free modulo every prime — and how often each one recurs is predicted, to within a few per cent, by a constant computed from nothing else.

   part 7 · number
8. 

   Euclid's proof run as a machine

   Euclid proved there is no last prime by multiplying the primes on any list, adding one, and noting that the result has a prime factor not on the list. Run the proof as a machine — start from 2, and each time take the smallest prime factor of one more than the product so far — and it produces 2, 3, 7, 43, 13, 53, 5, 6221671, … a sequence that never repeats, that reaches small primes late and large ones early, and that nobody can prove reaches every prime.

   part 8 · number
9. 

   When Euclid's number is itself prime

   Multiply the primes up to p and add one. Euclid needed only that the result has a prime factor beyond p; it is itself prime for p = 2, 3, 5, 7 and 11, and then not again until 31, and then not until 379. Up to 1,100 there are nine such primes of each sign, against thirteen that a careful estimate expects. The estimate predicts infinitely many and grows by about 1.8 every time x is multiplied by e; nobody can prove there is even one more.

   part 9 · number
10. 

    A constant that holds the primes

    There is a number A = 1.3063778838… such that A cubed, A to the ninth, A to the twenty-seventh and every further power of three, rounded down, is prime: 2, 11, 1361, 2521008887 and on for ever. W. H. Mills proved in 1947 that such a number exists. It looks like a formula for primes and is the opposite of one. Its digits are read off the primes it produces, each prime fixes about as many digits as it has, and the whole argument stands on a theorem about gaps between primes — which is why the power is 3 and not 2.

    part 10 · number
11. 

    Numbers that never make a prime

    Multiply 78,557 by a power of two and add one. The result is never prime, for any power, though almost every other odd number gives a prime within a few doublings. The reason is that seven small primes take it in turn to divide the result, on a schedule repeating every 36 steps that leaves no step uncovered. Proving nothing smaller does this has taken sixty years of search, and five candidates are still running.

    part 11 · number
12. 

    The comet Goldbach left behind

    Count the ways each even number is a sum of two primes, and the points do not form a smear. They split into bands: 12,000 has 302 ways and 12,002 has 115. One small product over odd prime factors explains every band and brings them all to a single line, and it says the count grows without bound. Nobody can prove the count is never nought.

    part 12 · number

All series