A big advance was made by Ernst Kummer, who proved the result when n is a so-called regular prime: this settled the argument for almost all values of n that are less than 100. Over the years more and more cases were settled, and by the mid-20th century Fermat’s conjecture had been proved for all values of n up to 2500, and by 1990 for all values up to 4 million. But there was still a long way to go!
In June 1993 Andrew Wiles, a British mathematician working at Princeton University in the US, announced to great excitement at a conference in Cambridge that he had proved Fermat’s last theorem. Although this turned out to be premature, as a gap was found in his argument, he eventually patched it up with the help of his former student, Richard Taylor. Wiles’s remarkable proof was published in 1995 to great acclaim. Fermat’s last theorem had at last been proved (see Figure 27).
27. A postage stamp celebrates Andrew Wiles’s proof of Fermat’s last theorem.
Chapter 6From cards to cryptography
In this chapter we introduce a fundamental theorem of Pierre de Fermat and apply it to a recreational problem on the shuffling of cards. We then present a generalization of Fermat’s result that’s due to Leonhard Euler, and a method of factorizing numbers that’s also due to Fermat. We conclude by applying Euler’s theorem to the sending of secret messages in cryptography, describing its use in ensuring the security of our credit cards.
Fermat’s little theorem
Over two thousand years ago, Chinese mathematicians supposedly observed that
This led them to claim that n divides if and only if n is prime. Is their claim true? In this section we’ll investigate this and similar questions.
In Chapter 4 we studied squares (mod p), where p is an odd prime, and we’ll now look at higher powers. We’ll start with the first few powers of 3 and 4 (mod 7):
noting, in particular, that and . It turns out, in fact, that if a is any integer that’s not divisible by 7, then : for example,
These results are special cases of a celebrated result that Pierre de Fermat announced in 1640, but which was first proved by Gottfried Leibniz sometime before 1683. It is usually called ‘Fermat’s little theorem’.
Fermat’s little theorem: If p is a prime, and if a is an integer that is not divisible by p, then .
For example, if and , then 17 is not divisible by 7, and so . This is correct, because .
It can further be shown that if , then k must be a factor of .
The idea of the proof of Fermat’s little theorem is to look at the first positive multiples of a and reduce them (mod p). For example, if and then the first six positive multiples of a are 3, 6, 9, 12, 15, and 18, and reducing them (mod 7) gives 3, 6, 2, 5, 1, 4. Likewise, if , then the multiples are 4, 8, 12, 16, 20, 24, and reducing them (mod 7) gives 4, 1, 5, 2, 6, 3. In each case we get a rearrangement of the numbers 1, 2, 3, 4, 5, and 6.
In general, the first positive multiples of a are
and when we reduce them (mod p) the results are all different; this is because if , for non-zero numbers m and n, then , after cancelling the term a on both sides (which we can do because a is coprime to p). So these non-zero multiples (mod p) are all different, and must therefore be the numbers , in some order.
We’ll now multiply these multiples together, giving
But, as we have just seen, these multiples are just in some order, and their product is
Equating these two products gives
and cancelling the terms (which are all coprime to p) gives
as we wished to prove.
In the statement of Fermat’s little theorem, we made the proviso that a is not divisible by p. We can remove this condition by multiplying both sides of the congruence by a, giving the following alternative form:
Fermat’s little theorem: If p is a prime and a is an integer, then .
Here we can omit the above proviso, because if a is divisible by p, then the result is still true, because both sides are congruent to 0 (mod p).
Can we turn things around? Is it true that if for all numbers a, then n must be a prime? This is usually the case but, as the London schoolteacher Robert Carmichael discovered in 1912, there are exceptions. The smallest example is where for all numbers a. Although there are infinitely many such ‘Carmichael numbers’, they seem to occur quite rarely, with only six others that are less than 10,000, and only forty-three up to one million.
Even if we restrict our attention to , there are exceptions: for example, , but is not prime. So the ancient Chinese were right in their claim above that n must divide when n is prime, but were wrong to assert that if n divides , then n must always be prime.Counting necklaces
As a brief diversion, we can also derive Fermat’s little theorem by counting necklaces! A necklace is a circular arrangement of coloured beads. How many different coloured necklaces are there if there are p beads (where p is prime) and a available colours, and if we use at least two colours?
Because of the circular arrangement of beads, each necklace
