wHITTy & wIlSON | 397
apparently taken with the problem and, as he had with problems in the past, mastered it at
breakneck speed, to the extent of believing he had solved it. He had at any rate got somewhat
further than Post and Markov: a semigroup with cancellation adds a little more structure, since
we may assume that pq = pr implies (via cancellation) that q = r.
If Turing failed to resolve the word problem for general groups, his Cambridge contem-
porary the famous group theorist Bernhard Neumann did no better! Neumann’s student,
J. L. Britton, recounts that:^9
At one time (probably 1949) he [Bernhard Neumann] believed he had discovered a proof of
the solvability of the word problem for groups; upon mentioning this to Turing, he was discon-
certed to learn that Turing had just completed a proof of its unsolvability. Both of them urgently
re-examined their proofs and both proofs were found to be wrong.
Prime numbers
Turing’s interest in the Riemann hypothesis originated in the 1930s, shortly after he arrived in
Cambridge. In 1932 the Cambridge mathematician A. E. Ingham wrote a classic text on prime
numbers. Turing purchased this in 1933 and started serious work on the subject around 1937.^10
A ‘prime number’ is a number, larger than 1, whose only factors are itself and
1: so 17 is a prime number, while 18 (= 2 × 2 × 3) is not. The primes up to 50 are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Note that we cannot write out a complete list of primes—they go on for ever. This celebrated
result appears in Book IX of Euclid’s Elements, and has one of the most attractive proofs in
mathematics. In modern language, we assume that the result is false—that there are only a finite
number of primes (say, p, q, . . . , and z)—and consider the number N = (p × q × . . . × z) + 1. Since
p × q × . . . × z is divisible by each of these primes, N cannot be divisible by any of them, and so
there must exist another prime—either N itself or one of its prime factors. This contradicts our
assumption that p, q, . . . , z are the only primes. So there are infinitely many primes.
Prime numbers are central to mathematics because they form the building blocks for
numbers—every whole number can be built up from them. So, for example, 60 = 2 × 2 × 3 × 5,
and, in general, every whole number splits into primes in only one way, apart from the order in
which we write down the factors.
How are the primes distributed? Although they generally seem to ‘thin out’ the further along
the list we proceed, they do not seem to be distributed in a regular manner. For example, pairs of
prime numbers differing by just 2 (such as 5 and 7, or 101 and 103) seem to crop up however far
we go, although this has never been proved. On the other hand, it is a simple matter to construct
arbitrarily long lists of non-primes. For numbers around 10 million, the hundred just below
contain nine primes (which is rather a lot), while the hundred just above contain only two.
In his inaugural lecture at the University of Bonn in 1975, the distinguished number theorist
Don Zagier said:^11
There are two facts of which I hope to convince you so overwhelmingly that they will per-
manently be engraved in your hearts. The first is that the prime numbers belong to the most
arbitrary objects studied by mathematicians: they grow like weeds, seeming to obey no other
law than that of chance, and nobody can predict where the next one will sprout. The second fact
is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning