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 2p 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 2341 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, np 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, 3341 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 10150 is prime, passing Fermat’s test just once means that the chances of the number being not prime are as low as 1 in 1043. So for the twins, probably one test was enough to give them the buzz of prime discovery.
Prime number hopscotch
This is a game for two players in which knowing your twin primes can give you an edge.
Write down the numbers from 1 to 100, or download the prime numbers hopscotch board from The Number Mysteries website. The first player takes a counter and places it on a prime number, which is at most five steps away from square 1. The second player takes the counter and moves it to a bigger prime that is at most five squares ahead of where the first player placed it. The first player follows suit, moving the counter to an even higher prime number which again is at most five squares ahead. The loser is the first player unable to move the counter according to the rules. The rules are: (1) the counter can’t be moved further than five squares ahead, (2) it must always be moved to a prime, and (3) it can’t be moved backwards or left where it is.
FIGURE 1.21 An example of a prime number hopscotch game where the maximum move is five steps.
The picture above shows a typical scenario. Player 1 has lost the game because the counter is at 23 and there are no primes in the five numbers ahead of 23 which are prime. Could Player 1 have made a better opening move? If you look carefully, you’ll see that once you’ve passed 5 there really aren’t many choices. Whoever moves the counter to 5 is going to win because they will at a later turn be able to move the stone from 19 to 23, leaving their opponent with no prime to move to. So the opening move is vital.
But what if we change the game a little? Let’s say that you are allowed to move the counter to a prime which is at most seven steps ahead. Players can now jump a little further. In particular, they can get past 23 because 29 is six steps ahead and within reach. Does your opening move matter this time? Where will the game end? If you play the game you’ll find that this time you have many more choices along the way, especially when there is a pair of twin primes.
At first sight, with so many choices it looks like your first move is irrelevant. But look again. You lose if you find yourself on 89 because the next prime after 89 is 97, eight steps ahead. If you trace your way back through the primes, you’ll find that being on 67 is crucial because here you get to choose which of the twin primes 71 and 73 you place the counter on. One is a winning choice; the other will lose you the game because every move from that point on is forced on you. Whoever is on 67 can win the game, and it seems that 89 is not so important. So how can you make sure you get there?
If you carry on tracing your way back through the game you’ll find that there’s a crucial decision to be made for anyone on the prime 37. From there, you can reach my daughters’ twin primes, 41 and 43. Move to 41, and you can guarantee winning the game. So now it looks as if the game is decided by whoever can force their opponent to move them to the prime 37. Continuing to wind the game back in this way reveals that there is indeed a winning opening move. Put the counter on 5, and from there you can guarantee that you get all the crucial decisions that ensure you get to move the stone to 89 and win the game because then your opponent can’t move.
What if we continue to make the maximum permitted jump even bigger: can we be always be sure that the game will end? What if we allow each player to move a maximum of 99 steps—can we be sure that the game won’t just go on for ever because you can always jump to another prime within 99 of the last one? After all, we know that there are infinitely many primes, so perhaps at some point you can simply jump from one prime to the next.
It is actually possible to prove that the game does always end. However far you set the maximum jump, there will always be a stretch of numbers greater than the maximum jump containing no primes, and there the game will end. Let’s look at how to find 99 consecutive numbers, none of which is prime. Take the number 100×99×98×97×…×3×2×1. This number is known as 100 factorial, and written as 100! We’re going to use an important fact about this number: if you take any number between 1 and 100, then 100! is divisible by this number.
Look at this sequence of consecutive numbers:
100!+2, 100!+3, 100!+4, …, 100!+98, 100!+99, 100!+100
100!+2 is not prime because it is divisible by 2. Similarly, 100!+3 is not prime because it is divisible by 3. (100! is divisible by 3, so if we add 3 it’s still divisible by 3.) In fact, none of these numbers is prime. Take 100!+53, which is not prime because 100! is divisible by 53, and if we add 53 the result is still divisible by 53. Here are 99 consecutive numbers, none of which is prime. The reason we started at 100!+2 and not 100!+1 is that with this simple method we can deduce only that 100!+1 is divisible by 1, and that won’t help us to tell whether it’s prime. (In fact it isn’t.)
This website has information about where the hopscotch game will end for larger and larger jumps: http://bit.ly/Primehopscotch You can use your smartphone to scan this code.
So we know for certain that if we set the maximum jump to 99, our prime number hopscotch game will end at some point. But 100! is a ridiculously large number. The game actually finished way before this point: the first place where a prime is followed by 99 non-primes is 396,733.
Playing this game certainly reveals the erratic way in which the primes seem to be scattered through the universe of numbers. At first sight there’s no way of knowing where to find the next prime. But if we can’t find a clever device for navigating from one prime to the next, can we at least come up with some clever formulas to produce primes?
Could rabbits and sunflowers be used to find primes?
Count the number of petals on a sunflower. Often there are 89, a prime number. The number of pairs of rabbits after 11 generations is also 89. Have rabbits and flowers discovered some secret formula for finding primes? Not exactly. They like 89 not because it is prime, but because it is one of nature’s other favourite numbers: the Fibonacci numbers. The Italian mathematician Fibonacci of Pisa discovered this important sequence of numbers in 1202 when he was trying to understand the way rabbits multiply (in the biological rather than the mathematical sense).
Fibonacci
