Читать книгу The Number Mysteries: A Mathematical Odyssey through Everyday Life - Marcus Sautoy du - Страница 20

If we can’t write down the primes in one big table, then perhaps we can try to find some pattern to help us to generate the primes. Is there some clever way to look at the primes you’ve got so far, and know where the next one will be?

Here are the primes we discovered by using the Sieve of Eratosthenes on the numbers from 1 to 100:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,

59, 61, 67, 71, 73, 79, 83, 89, 97

The problem with the primes is that it can be really difficult to work out where the next one will be, because there don’t seem to be any patterns in the sequence that will help us to help locate them. In fact, they look more like a set of lottery ticket numbers than the building blocks of mathematics. Like waiting for a bus, you can have a huge gap with no primes and then suddenly several come along in quick succession. This behaviour is very characteristic of random processes, as we shall see in Chapter 3.

Apart from 2 and 3, the closest that two prime numbers can be is two apart, like 17 and 19 or 41 and 43, since the number between each pair is always even and therefore not prime. These pairs of very close primes are called twin primes. With my obsession for primes, my twin daughters almost ended up with the names 41 and 43. After all, if Chris Martin and Gwyneth Paltrow can call their baby Apple, and Frank Zappa can call his daughters Moon Unit and Diva Thin Muffin Pigeen, why can’t my twins be 41 and 43? My wife was not so keen, so these have had to remain my ‘secret’ middle names for the girls.

Although primes get rarer and rarer as you move out into the universe of numbers, it’s extraordinary how often another pair of twin primes pops up. For example, after the prime 1,129 you don’t find any primes in the next 21 numbers, then suddenly up pop the twin primes 1,151 and 1,153. And when you pass the prime 102,701 you have to plough through 59 non-primes, and then the pair of primes 102,761 and 102,763 suddenly appear. The largest twin primes discovered by the beginning of 2009 have 58,711 digits. Given that it only takes a number with 80 digits to describe the number of atoms in the observable universe, these numbers are ridiculously large.

But are there more beyond these two twins? Thanks to Euclid’s proof, we know that we’re going to find infinitely many more primes, but are we going to keep on coming across twin primes? As yet, nobody has come up with a clever proof like Euclid’s to show why there are infinitely many of these twin primes.

At one stage it seemed that twins might have been the key to unlocking the secret of prime numbers. In The Man Who Mistook His Wife for a Hat, Oliver Sacks describes the case of two real-life autistic savant twins who used the primes as a secret language. The twin brothers would sit in Sacks’s clinic, swapping large numbers between themselves. At first Sacks was mystified by their dialogue, but one night he cracked the secret to their code. Swotting up on some prime numbers of his own, he decided to test his theory. The next day he joined the twins as they sat exchanging six-digit numbers. After a while Sacks took advantage of a pause in the prime number patter to announce a seven-digit prime, taking the twins by surprise. They sat thinking for a while, since this was stretching the limit of the primes they had been exchanging to date, then they smiled simultaneously, as if recognizing a friend.

During their time with Sacks, they managed to reach primes with nine digits. Of course, no one would find it remarkable if they were simply exchanging odd numbers or perhaps even square numbers, but the striking thing about what they were doing is that the primes are so randomly scattered. One explanation for how they managed it relates to another ability the twins had. Often they would appear on television, and impress audiences by identifying that, for example, 23 October 1901 was a Wednesday. Working out the day of the week from a given date is done by something called modular or clock arithmetic. Maybe the twins discovered that clock arithmetic is also the key to a method that identifies whether a number is prime.

If you take a number, say 17, and calculate 2¹⁷, then if the remainder when you divide this number by 17 is 2, that is good evidence that the number 17 is prime. This test for primality is often wrongly attributed to the Chinese, and it was the seventeenth-century French mathematician Pierre de Fermat who proved that if the remainder isn’t 2, then that certainly implies that 17 is not prime. In general, if you want to check that p is not a prime, then calculate 2^p and divide the result by p. If the remainder isn’t 2, then p can’t be prime. Some people have speculated that, given the twins’ aptitude for identifying days of the week, which depends on a similar technique of looking at remainders on division by 7, they may well have been using this test to find primes.

At first, mathematicians thought that if 2^p does have remainder 2 on division by p, then p must be prime. But it turns out that this test does not guarantee primality. 341=31×11 is not prime, yet 2³⁴¹ has remainder 2 on division by 341. This example was not discovered until 1819, and it is possible that the twins might have been aware of a more sophisticated test that would wheedle out 341. Fermat showed that the test can be extended past powers of 2 by proving that if p is prime, then for any number n less than p, n^p always has remainder n when divided by the prime p. So if you find any number n for which this fails, you can throw out p as a prime impostor.

For example, 3³⁴¹ doesn’t have remainder 3 on division by 341—it has remainder 168. The twins couldn’t possibly have been checking through all numbers less than their candidate prime: there would be too many tests for them to run through. However, the great Hungarian prime number wizard Paul Erdos estimated (though he couldn’t prove it rigorously) that to test whether a number less than 10¹⁵⁰ is prime, passing Fermat’s test just once means that the chances of the number being not prime are as low as 1 in 10⁴³. So for the twins, probably one test was enough to give them the buzz of prime discovery.