It was a wonderful argument. Euclid had no idea how to produce primes explicitly, but he could prove why they would never run dry. It is striking that we do not know whether infinitely many of Euclid’s numbers themselves are prime, even though they are sufficient to prove that there must be an infinite number of primes. With Euclid’s proof, gone was the chance of fitting together a Periodic Table listing all the primes or of discovering some prime number genome coding billions of them. No simple butterfly collecting would ever allow us to understand these numbers. Here, then, was the ultimate challenge: the mathematician, armed with a limited weaponry, pitched against the infinite expanse of prime numbers. How could we possibly chart a path through such an infinite chaotic jumble and find some pattern which might predict their behaviour?
Hunting for primes
Generations have striven without success to improve on Euclid’s understanding of the primes, and there have been many intriguing speculations. But as Cambridge don Hardy liked to say, ‘Every fool can ask questions about prime numbers that the wisest man cannot answer.’ The Twin Primes Conjecture, for example, asks whether there are infinitely many primes p such that the number p + 2 is also prime. An example of such a pair is 1,000,037 and 1,000,039. (Note that this is the closest that two primes numbers can be, since N and N + 1 cannot both be prime – except when N = 2 – because at least one of these numbers is divisible by 2.) Might Sacks’s autistic-savant twins have had an extra facility for finding these twin primes? Euclid proved two millennia ago that there are infinitely many primes, but no one knows whether there might be some number beyond which there are no longer such close primes. We believe that there are infinitely many twin primes. Guesses are one thing, but proof remains the ultimate goal.
Mathematicians tried, with varying degrees of success, to come up with formulas that, even if they don’t generate all prime numbers, do produce a list of primes. Fermat thought he had one. He guessed that if you raise 2 to the power 2N and add 1, the resulting number
Fermat’s numbers were very dear to Gauss’s heart. The fact that 17 is one of Fermat’s primes is the key to why Gauss could construct his perfect 17-sided shape. In his great treatise Disquisitiones Arithmeticae, Gauss shows why it is that, if the Nth Fermat number is a prime, you can make a geometric construction of an N-sided shape only using a straight edge and compass. The fourth Fermat number, 65,537, is prime, so with these very basic instruments it is possible to construct a perfect 65,537-sided figure.
Fermat’s numbers have failed to throw up more than four primes to date, but he had more success in uncovering some of the very special properties that prime numbers have. Fermat discovered a curious fact about those prime numbers that leave remainder 1 on division by 4 – examples are 5, 13, 17 and 29. Such prime numbers can always be written as the sum of two squares – for example, 29 = 22 + 52. This was another of Fermat’s teases. Although he claimed to have a proof, he failed to record much of the details.
On Christmas Day, 1640, Fermat wrote of his discovery – that certain primes could be expressed as the sum of two squares – in a letter to a French monk called Marin Mersenne. Mersenne’s interests were not confined to liturgical matters. He loved music and was the first to develop a coherent theory of harmonics. He also loved numbers. Mersenne and Fermat corresponded regularly about their mathematical discoveries, and Mersenne broadcast many of Fermat’s claims to a wider audience. Mersenne became renowned for his role as an international scientific clearing house through which mathematicians could disseminate their ideas.
Just as generations had been captivated by the search for order in the primes, Mersenne too had caught the bug. Although he couldn’t see a way to find a formula that would produce all the primes, he did come across a formula that in the long run has proved far more successful at finding primes than Fermat’s formula has. Like Fermat, he started by considering powers of 2. But instead of adding 1, as Fermat had, Mersenne decided to subtract 1 from the answer. So, for example, 23 − 1 = 8 − 1 = 7, a prime number. Maybe Mersenne’s musical intuition was coming to his aid. Doubling the frequency of a note takes the note up an octave, so powers of 2 produce harmonic notes. You might expect a shift of 1 to sound a very dissonant note, not compatible with any previous frequency – a ‘prime note’.
Mersenne quickly discovered that his formula wasn’t going to yield a prime every time. For example, 24 − 1 = 15. Mersenne realised that if n was not prime then there was no chance that 2n − 1 was going to be prime. But now he boldly claimed that, for n up to 257, 2n − 1 would be prime precisely if n was one of the following numbers: 2, 3, 5, 7, 13, 19, 31, 67, 127, 257. He had discovered that even if n was prime, it still annoyingly didn’t guarantee that his number 2n − 1 would be prime. He could calculate 211 − 1 by hand and get 2,047, which is 23 × 89. Generations of mathematicians marvelled at Mersenne’s ability to assert that a number as large as 2257 − 1 was prime. This number has 77 digits. Did the monk have access to some mystical arithmetic formula that told him why this number, beyond any human computational abilities, was prime?
Mathematicians believe that if one continues Mersenne’s list, there will be infinitely many choices for n which will make Mersenne’s numbers 2n − 1 into prime numbers. But we are still missing a proof that this guess is true. We are still waiting for a modern day Euclid to prove that Mersenne’s primes never run dry. Or perhaps this far-off peak is just a mathematical mirage.
Many mathematicians of Fermat and Mersenne’s generation had played around with interesting numerological properties of the primes, but their methods did not match up to the ancient Greek ideal of proof. This explains in part why Fermat gave no details of many of the proofs he claimed to have discovered. There was a distinct lack of interest during this period in providing such logical explanations. Mathematicians were quite content with a more experimental approach to their subject, where in an increasingly mechanised world results were justified by their practical applications. In the eighteenth century, however, there arrived a mathematician who would rekindle a sense of the value of proof in mathematics. The Swiss mathematician Leonhard Euler, born in 1707, came up with explanations for many of the patterns that Fermat and Mersenne had discovered but failed to account for. Euler’s methods would later play a significant role in opening new theoretical windows onto our understanding of the primes.
Euler, the mathematical eagle
The mid-eighteenth century was a time of court patronage. This was pre-Revolutionary Europe, when countries were ruled by enlightened despots: Frederick the Great in Berlin, Peter the Great and Catherine the Great in St Petersburg, Louis XV and Louis XVI in Paris. Their patronage supported the academies that drove the intellectual development of the Enlightenment, and indeed they saw it as a mark of their standing that they be surrounded in their courts by intellectuals. And they were well aware of the potential of the sciences and mathematics to boost the military and industrial capabilities of their countries.
Euler