Number Theory: A Very Short Introduction

by Robin Wilson

  For example, knowing that and , we can take , , , and , giving

  or, on rewriting , we could take , , , and , giving

  So some numbers can be written as the sum of two squares in more than one way: another example is

  It follows from the above multiplication rule that if we can first decide which prime numbers can be written as the sum of two squares, then by combining them we can work out which numbers in general can be written in this way. This is another instance of the use of prime numbers as the building blocks for numbers in general. We now proceed to investigate the representation of prime numbers as the sum of two squares.

  We have seen that , and that the odd primes of the form cannot be written as the sum of two squares. But what about the odd primes of the form ? We can certainly write:

  This list illustrates the following general rule, which was first stated by Albert Girard in 1625 and in a letter from Fermat to Mersenne on Christmas Day 1640, and was eventually proved by Euler in 1754:

  An odd prime number p can be written as the sum of two squares if and only if p has the form . Moreover, this can be done in only one way, apart from the order in which the two squares appear.

  Before leaving this section, we ask a related question:

  Which numbers can be written as the difference of two perfect squares?

  This question is much easier to answer. Let’s look at some examples:

  But 2, 6, 10, … cannot be written in this way, and it seems as though the following general rule applies:

  Difference of two squares: A number can be written as the difference of two squares except when it has the form .

  To see why this is, we note again that every perfect square has the form 4n or , and so the difference between two squares must have the form 4n, , or . So the difference between two squares can never be of the form . Moreover,

  if , then we can write

  if , then we can write

  and if , then we can write

  So every number can indeed be written as the difference of two squares, except when it has the form .

  Sums of more squares

  We’ve seen that we cannot write every number as the sum of just two squares. Can we write every number as the sum of three squares (zero being allowed)? Certainly we have

  But we cannot write 7 or 15 as the sum of only three squares. To see why, we note that every odd square has the form (see Chapter 2), and that every even square, being divisible by 4, has the form 8n or . But we cannot combine three numbers of the form 8n, , or to give a number of the form . Diophantus had claimed this result 1700 years ago, and Fermat proposed the following more general result, which was proved by Legendre in 1798:

  Sum of three squares: Every number can be written as the sum of three squares, except when it has the form , for some integers m and k.

  For example,

  cannot be written as the sum of three squares, and nor can their multiples,

  But these numbers can all be written as the sum of four squares: for example,

  In fact, every positive integer without exception can be written as the sum of four squares. This remarkable result was stated by Claude Bachet de Méziriac in 1621, and was proved by Joseph-Louis Lagrange using ideas of Euler:

  Lagrange’s four-square theorem: Every number can be written as the sum of four squares.

  As with Fermat’s earlier result on the sum of two squares, it is enough to prove this for prime numbers only, and then to use a multiplication rule to obtain the general result. This rule, discovered by Euler, states that if m and n can each be written as the sum of four squares, then so can their product mn. This is because, for and , we have

  For example, knowing that and , we can take , , , , , , , and , and write as a sum of four squares as follows:

  Higher powers

  Having looked at sums of squares, we now turn our attention to sums of cubes and higher powers. A well-known story concerns the Cambridge mathematician G. H. Hardy who in 1918 was visiting his friend and colleague Srinivasa Ramanujan, one of the most intuitive mathematicians of all time, who was seriously ill in hospital. Together they’d solved some important problems in number theory. Hardy, finding it difficult to think of anything to say, remarked that his taxicab to the hospital had the number 1729 which seemed to be rather a dull number. As Hardy recalled, Ramanujan replied: ‘No, Hardy! It is a very interesting number. It is the smallest number expressible as the sum of two cubes in two different ways.’(These are and .)

  Waring’s problem

  As we have seen, Lagrange’s four-square theorem asserts that every number can be written as the sum of four squares. In 1770 the Cambridge mathematician Edward Waring suggested that there were similar results for higher powers, claiming the following results for cubes and fourth powers:

  Every number can be written as the sum of nine cubes.

  Every number can be written as the sum of nineteen fourth powers.

  Waring’s claims were correct, and cannot be improved because there are numbers that actually require nine cubes and nineteen fourth powers, such as

  for cubes:

  for fourth powers:

  Waring asked whether these ideas can be extended to higher powers:

  Waring’s problem: For each positive integer k, does there exist a number g(k) such that every number can be written as the sum of g(k) kth powers?

  For example, , by Lagrange’s four-square theorem, and the results just asserted tell us that and . Other known values are for sums of fifth powers, and for sums of sixth powers. In 1909, the German mathematician David Hilbert answered Waring’s question in the affirmative by proving that there is such a number g(k) for each value of k.

  What can we say about g(k)? Around 1772, Johann Albrecht Euler, Leonhard’s eldest son, suggested that

  where ⌊x⌋ is the integer part of x: for example, .

  Note that,

  so this bound gives the correct value for g(k) in these two cases. It has since been proved to give the right answer for all values of k up to 471.6 million, and with all this evidence it’s believed to be correct in every case, although this has never been proved.

  But we can say more. When , it turns out that only two numbers (23 and 239) actually need nine cubes, and that only a finite number need eight cubes. So we can say that,

  From some point onwards, every number can be written as the sum of just seven cubes.

  It is also believed, although this has never been proved, that the number of cubes can be reduced further, possibly even to four.

  For fourth powers it can be proved that,

  From some point onwards, every number can be written as the sum of just sixteen fourth powers.

  Corresponding results can be proved for higher powers.

  Fermat’s last theorem

  We conclude this chapter with a brief account of one of the most famous achievements in number theory—the proof of Fermat’s last theorem.

  In our discussion of Pythagorean triples, we saw how to find integer solutions of the Diophantine equation

  Can we likewise find integer solutions to the equations

  and in general,

  We can make a couple of general observations.

  First, there are always ‘trivial’ solutions, in which one of the numbers a, b, and c is 0: for example,

  In what follows we’re interested only in positive solutions.

  Secondly, suppose that we knew that there were no integer solutions of the equation . Then we could deduce that the same is true when the exponent is any multiple of 3. For example, the equation could then have no integer solutions, because we can rewrite it as

  which we’ve assumed to have no solutions. So, when investigating solutions of the equation , we can restrict our attention to the cases when n is 4 or a prime number.

  Fermat became interested in the problem while reading a Latin translation of Diophantus’s Arithmetica that had been published by Claude Bachet de la Méziriac in 1621 (see Figu
re 26). In the section on Pythagorean triples Fermat added a now-famous marginal comment:

  On the other hand, it is impossible for a cube to be written as a sum of two cubes or a fourth power to be written as a sum of two fourth powers or, in general, for any number which is a power greater than the second to be written as a sum of two like powers. I have a truly marvellous proof of this proposition which this margin is too narrow to contain.

  26. Bachet’s translation of Diophantus’s Arithmetica.

  This is often called ‘Fermat’s last theorem’, because it became the last of Fermat’s assertions to be proved—but it should perhaps have been called ‘Fermat’s conjecture’:

  Fermat’s last theorem. The equation has no positive integer solutions when .

  Most mathematicians believe that Fermat couldn’t have had a valid proof of his conjecture. Many attempts have since been made to find one, and the belief is that, if he really had found a correct argument, then it would surely have been rediscovered over the ensuing years.

  Fermat himself proved that the equation can have no integer solutions. To do so, he invented a method of proof known as the method of infinite descent, showing by an algebraic argument that if this equation (or, more precisely, one closely related to it) had a solution in positive integers, then there would be another solution that involved smaller numbers than before. By repeating this argument over and over again, he’d then get smaller and smaller positive solutions—but this cannot happen indefinitely. This contradiction shows that the original solution couldn’t have existed in the first place.

  More than a century later, in 1770, Euler produced a proof for the case , but it had a gap in it that was subsequently filled by Legendre.

  Major advances were made in the 1820s by Sophie Germain, a self-taught mathematician who made several substantial contributions to number theory and to the theory of elasticity. Interested in primes p for which is also prime (such as 2, 3, 5, 11, and 23), she proved several results concerning them—for example, that if , then one of a, b, and c must be divisible by , and one of them must be divisible by p2. Then Legendre and Lejeune Dirichlet proved the theorem when , using her results, and in 1835 Gabriel Lamé of Paris proved it for .

  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 6

  From 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 can be counted in p ways, depending on where we start: for example, the necklace in Figure 28 arises from five different strings of beads,

  28. A necklace with five beads.

  where R, B, and Y stand for red, blue, and yellow.

  How many different necklaces can there be? Because there are p beads in up to a colours, there are ap possible strings of beads, or strings when we exclude the a single-colour ones (such as RRRRR) that can each be coloured in only one way. But each necklace arises from p different strings, and so the number of different necklaces is . Because this must be an integer, must be divisible by p—that is, , which is Fermat’s little theorem.

  Shuffling cards

  An amusing application of Fermat’s result is to the shuffling of cards (sometimes
called ‘Faro shuffling’). Starting with a normal pack of cards we first cut it into two piles, so that the cards in one pile are in positions 1 to 26 and those in the other pile are in positions 27 to 52. We now shuffle the cards so that the cards in positions 1, 2, 3, …, 26 are moved to positions 2, 4, 6, …, 52, and the cards in positions 27, 28, 29, …, 52 are moved to positions 1, 3, 5, …, 51, giving the new ordering

  (see Figure 29). It follows, as we can easily check, that for each a, the card initially in position a has moved to the new position 2a (mod 53).

  29. Shuffling cards.

  How many shuffles are needed to restore the pack of cards to its original order? After n shuffles, the card initially in position a has moved to position (mod 53), so after the pack has been restored to its original order, for all numbers a. Now gcd , so we can cancel the a, giving us . But by Fermat’s little theorem, , so the pack is certainly restored to its original order after 52 shuffles.

  But can this happen earlier? If so, the number of shuffles must be a factor of 52, by our remark following the first statement of Fermat’s result—that is, 2, 4, 13, or 26. But, after some calculation, we find that

  None of these works, so the order of the cards is restored for the first time after 52 shuffles.