Number Theory: A Very Short Introduction

by Robin Wilson

  34. Summing the powers of

  In the same way, we can show that the infinite series

  whose denominators are the powers of 3, converges to , and that the infinite series

  whose denominators are the powers of 5, converges to , More generally, we can show that, for any number p,

  We’ll need this result later on.

  Not all infinite series converge. A celebrated example is the so-called harmonic series

  whose denominators are the positive integers. To see why it doesn’t have a finite sum we’ll group the terms as

  Now this sum is larger than the following sum:

  which equals  , because each group of terms has sum .

  But the sum of this latter series increases without limit as we add more terms, and the harmonic series has an even larger sum and so it cannot have a finite sum either.

  So the harmonic series doesn’t converge: and surprisingly, as Euler proved in 1737, even if we throw away most of its terms and leave only those whose denominators are primes—that is,

  —then there is still no finite sum.

  The zeta function

  In the early 18th century a celebrated challenge was to find the exact sum of the infinite series

  whose denominators are the squares, 1, 4, 9, 16, 25, … . The Swiss mathematician Johann Bernoulli, then possibly the world’s greatest mathematician, failed to solve the problem, and it was eventually answered by his former pupil, Leonhard Euler, who proved that this series converges to π2/6, a remarkable result in that it involves the ‘circle number’ π. As Euler proudly observed:

  Quite unexpectedly I have found an elegant formula involving the quadrature of the circle.

  In the same way, Euler proved that:

  when the denominators are the fourth powers, the sum is π4/90,

  when the denominators are the sixth powers, the sum is π6/945,

  and when the denominators are the eighth powers, the sum is π8/9450.

  He subsequently continued his calculations up to the twenty-sixth powers. Here the sum is

  which he calculated correctly.

  When the denominators are the nth powers, Euler denoted the sum as ζ(n), where ζ is the Greek letter zeta, and named it the zeta function—that is,

  So ζ(1) is undefined (because the harmonic series has no finite sum), but , , , etc. It turns out that the series for ζ(n) converges for every number n that is greater than 1.

  Although the zeta function ζ(n) may seem to have nothing in common with prime numbers, Euler spotted a crucial connection, which we now explore. This connection can be used to give another proof that the list of primes is never-ending.

  The zeta function and prime numbers

  We can write the series for ζ(1) as follows:

  where each bracket involves the powers of just one prime number. This is because, by unique factorization, each term 1/n in the series for ζ(1) appears exactly once in the product on the right: for example,

  We now sum the series in each bracket, using our earlier result that

  this gives

  We can use this product to prove that there are infinitely many primes. For, if there were only finitely many primes, then the right-hand side would be a finite product, and so would have a fixed value. But this would require ζ(1) to have this same value, which is impossible because it is undefined. So there must be infinitely many primes.

  Euler extended these ideas to prove that, for any number n that’s greater than 1,

  This remarkable result is called the Euler product, and provides an unexpected link between the zeta function, which involves powers of numbers and seems to have nothing to do with primes, and a product that intimately involves all the prime numbers. It was a major breakthrough.

  Complex numbers

  Before we present the Riemann hypothesis, we’ll also need the idea of a complex number. This involves i, the ‘imaginary’ square root of −1, which we met briefly in Chapter 7.A complex number is a symbol of the form ; x is called the real part of the complex number, and y is the imaginary part. Examples of complex numbers are (which equals ), and 3 (which can be thought of as ).

  We can represent complex numbers geometrically as points on the ‘complex plane’. This two-dimensional picture consists of all points (x, y), where (x, y) represents the complex number ; for example, the points , and (3, 0) represent the complex numbers , and 3 (see Figure 35).

  35. Points on the complex plane.

  The Riemann hypothesis

  We’ve now set the scene for the Riemann hypothesis.

  As we’ve seen, the zeta function ζ(n) is defined for any number n that is greater than 1. But can we define it for other numbers n too? For example, how might we define ζ(0) or ζ(−1)? We can’t define them by the same infinite series, because we’d then have

  and

  and neither of these series has a finite sum. So we’ll need to find some other way.

  As a clue to how to proceed, we can show that, for certain values of x,

  we’ve already seen that this is true when . But it can be shown that the series on the left-hand side converges only when x lies between −1 and 1, whereas the formula on the right-hand side has a value for any x, apart from 1 (when we get 1/0, which is undefined). So we can extend the definition of the series on the left-hand side to all values of x (other than 1) by redefining it as the formula on the right-hand side.

  In the same way, Riemann found a way of extending the above infinite series definition of the zeta-function to all numbers x other than 1 (including 0 and −1). But he went much further than this. Using a technique called ‘analytic continuation’, Riemann extended the definition of the zeta function to all complex numbers other than 1 (because ζ(1) is undefined) in such a way that when k is a real number greater than 1, we get the same value as before. Because of this, the function is now known as the Riemann zeta function.

  In Chapter 7 we saw Gauss’s attempt to explain why the primes thin out on average, by proposing the estimate x/log x for the number of primes up to x. Riemann’s great achievement was to obtain an exact formula for the number of primes up to x, and his formula involved in a crucial way the so-called zeros of the zeta function—that is, the complex numbers z that satisfy the equation . But where are these zeros?

  It turns out that when ; these are called the trivial zeros of the zeta function. All the other zeros of the zeta function, the non-trivial zeros, are known to lie within a vertical strip between and (the so-called critical strip), as shown in Figure 36. As we move away from the horizontal axis, the first few non-trivial zeros occur at the following points:

  36. The zeros of the Riemann zeta function in the complex plane.

  Here, the imaginary parts (such as 14.1) are approximate, but the real parts are all equal to . Because all of these points all have the form multiple of i, the question arises:

  Does every zero of the Riemann zeta function in the critical strip lie on the line x= ?

  The Riemann hypothesis is that the answer to this question is ‘yes’. It has been proved that the zeros in the critical strip are symmetrically placed, both above and below the x-axis and on either side of the line , and that as we progress vertically up and down the line , many zeros do lie on it—in fact, the first trillion zeros lie on this line! But do all of the non-trivial zeros lie on the line , or might the first trillion be just a coincidence?

  It’s now generally believed that all the non-trivial zeros do lie on this line, but proving this is one of the most difficult unsolved challenges throughout the whole of mathematics. Indeed no-one has yet been able to prove the Riemann hypothesis, even after a century and a half. The million dollar prize is still up for grabs!

  Consequences

  If the actual statement of the Riemann hypothesis seems an anticlimax after the big build-up, its consequences are substantial. Recalling Riemann’s discovery of the role that the zeta function’s zeros play in the prime-counting function π(x) and in his exact
formula (involving the zeta function) for the number of primes up to x, we note that any divergence of these zeros from the line would crucially affect Riemann’s exact formula, because our understanding about how the prime numbers behave is so tied up in this formula. Indeed, finding just one zero off the line would cause major havoc in number theory—and in fact throughout mathematics: for a mathematician, truth must be absolute, and admitting even a single exception is forbidden. The prime number theorem would still be true, but would lose its influence on the primes. Instead of Don Zagier’s ‘military precision’, mentioned in Chapter 7, the primes would be found to be in full mutiny!

  We conclude this chapter with an unexpected development. In 1972 the American number theorist Hugh Montgomery was visiting the tea-room at Princeton’s Institute for Advanced Study and found himself sitting opposite the celebrated physicist Freeman Dyson. Montgomery had been exploring the spacings between the zeros on the critical line, and Dyson said ‘But those are just the spacings between the energy levels of a quantum chaotic system’. If this analogy indeed holds, as many think possible, then the Riemann hypothesis may well have consequences in quantum physics. Conversely, using their knowledge of these energy levels, quantum physicists rather than mathematicians may be the ones to prove the Riemann hypothesis. This is truly an intriguing thought!

  Chapter 9

  Aftermath

  In the previous seven chapters we have explored a range of topics from number theory, and we can now return to the questions that we raised in Chapter 1. Most of these questions we were able to answer, while a few others turned out to be famous problems that remain unresolved. For each question we refer back to the chapter in which it was discussed.

  The first ten questions

  We opened Chapter 1 by posing ten questions.

  In which years does February have five Sundays?

  Questions that ask for the day of the week on which a particular event falls have a long history, and their solutions often involve the idea of congruence. As we saw in Chapter 4, February has five Sundays in the years 2004, 2032, 2060, and 2088. Also, because 2000 was a leap year, we can find the corresponding years in the previous century by subtracting multiples of 28 years from 2004; those years were 1976, 1948, and 1920. The corresponding years for other centuries can be found in a similar way.

  What is special about the number 4,294,967,297?

  This number is . As we saw in Chapter 3, Pierre de Fermat believed that all numbers of the form , where n is a power of 2, are prime (the so-called ‘Fermat primes’), and this number, where , was the smallest that he was unable to check. Years later Leonhard Euler showed that it is not prime, and that 641 is a factor.

  How many right-angled triangles with whole-number sides have a side of length 29?

  Triples of numbers (a, b, c) for which a, b, and c are whole numbers and are called Pythagorean triples, and correspond to side-lengths of right-angled triangles. As we discovered in Chapter 5, there are only two such Pythagorean triples in which one side has length 29: these are (20, 21, 29) and (29, 420, 421).

  Are any of the numbers 11, 111, 1111, 11111, . . . perfect squares?

  In Chapter 2 we showed that all perfect squares must have the form 4n or , for some integer n. The numbers in this question all have the form , and so none of them can be a perfect square.

  I have some eggs. When arranged in rows of 3 there are 2 left over, in rows of 5 there are 3 left over, and in rows of 7 there are 2 left over. How many eggs are there altogether?

  In Chapter 4 we discussed the solution of simultaneous linear congruences, and gave this problem as an example. It is a version of Sunzi’s problem, and asks for the solution of the simultaneous congruences , , and . The smallest solution is , and other answers are found by adding multiples of .

  Can one construct a regular polygon with 100 sides if measuring is forbidden?

  In Chapter 3 we noted a connection between the construction of regular polygons and the Fermat primes mentioned above: this is Gauss’s result that a regular polygon with n sides can be constructed by an unmarked ruler and compasses if and only if n is the product of a power of 2 and unequal Fermat primes. But , where the Fermat prime 5 is repeated, and so a regular polygon with 100 sides cannot be so constructed.

  How many shuffles are needed to restore the order of the cards in a pack with two Jokers?

  Questions involving the shuffling of cards can be answered with help from Fermat’s little theorem on primes, as we described in Chapter 6. In this case, where there are 54 cards, the answer is 20 shuffles.

  If I can buy partridges for 3 cents, pigeons for 2 cents, and two sparrows for a cent, and if I spend 30 pence on buying 30 birds, how many birds of each kind must I buy?

  This is a Diophantine problem requiring an integer solution. As we discussed in Chapter 5, the solution involves two linear equations in three unknowns, together with the extra requirement that the number of each kind of bird that I buy must be a positive integer. The only answer is 5 partridges, 3 pigeons, and 22 sparrows.

  How do prime numbers help to keep our credit cards secure?

  In Chapter 6 we saw that multiplying large primes is usually a simple matter, whereas trying to factorize large numbers into their prime factors is not. The RSA method of encryption and decryption recognizes this difficulty and involves Euler’s theorem, a generalization of Fermat’s little theorem.

  What is the Riemann hypothesis, and how can I earn a million dollars?

  The Riemann hypothesis (or conjecture) was discussed in Chapter 8, and is one of the most famous unsolved problems in mathematics. The conjecture is closely related to that of locating the places where a certain function (called the ‘zeta function’) has a zero value. It turns out that its proof would tell us much about how prime numbers are distributed, as well as providing its solver with lasting fame and an award of one million dollars by the Clay Mathematics Institute.

  Integers

  How can we recognize whether a given number, such as 12,345,678, is a multiple of 8? or of 9?  or of 11? or of 88?

  In Chapter 2 we discussed several tests for divisibility by various numbers, such as 8, 9, and 11. The given number is not a multiple of 8 because the number given by its last three digits (678) is not divisible by 8. The sum of its digits is 36, which is divisible by 9, and so the given number is divisible by 9. The alternating sum of its digits is −4, which is not divisible by 11, and so the given number is not divisible by 11 or by any of its multiples, such as 88.

  Squares and cubes

  We discussed various topics related to squares and higher powers in Chapters 2 and 5. The next three questions were answered in the section on Squares in Chapter 2.

  Do any squares end in 2, 3, 7, or 8?

  We showed that all squares must end in 0, 1, 4, 5, 6, or 9, and so there can be no squares that end in 2, 3, 7, or 8.

  Must all squares be of the form 4n or , where n is an integer?

  As mentioned above, we showed that all squares must be of these forms—in particular, squares of even numbers all have the form 4n, and squares of odd numbers all have the form . We can also express this by saying that all squares must be congruent to 0 or 1 (mod 4).

  Must the sum of the first few odd numbers, 1, 3, 5, 7, …, always be a square?

  For any number k, the first k odd numbers are 1, 3, 5, …, , and on adding these numbers together we find that their sum is k2. So the sum of the first few odd numbers is always a square.

  The next two questions were discussed in Chapter 5, where we investigated which numbers can be written as the sum of two or more squares.

  Which numbers can be written as the sum of two squares?

  Because every square is congruent to 0 or 1 (mod 4), the sum of two squares must be congruent to 0, 1, or 2 (mod 4). So no number that is congruent to 3 (mod 4) can be a perfect square. More generally, as stated by Fermat and proved by Legendre, a number can be written as the sum of two squares if and only if every prime factor
that is congruent to 3 (mod 4) occurs to an even power.

  Can 9999 be written as the sum of two squares? or of three squares? or of four squares?

  It follows from our discussions that 9999 cannot be written as the sum of two squares because , or as the sum of three squares because . But, as proved by Lagrange, every positive integer can be written as the sum of four squares: for example, 9999 can be written as or as .

  Chapter 5 also contained a discussion of which right-angled triangles have sides whose lengths are all integers.

  Which right-angled triangles have integer-length sides?

  For a right-angled triangle to have integer-length sides, these lengths must be of the form , where k is a constant, x and y are coprime integers with one odd and the other even, and . Chapter 5 includes a table of all triples with (the so-called ‘primitive triples’) and no numbers exceeding 100.

  In Chapters 2 and 5 our discussions then extended to cubes.

  Must all cubes be of the form 9n, , or , where n is an integer?

  The answer to this question is ‘yes’, as we proved in Chapter 2, at the end of the section on Squares. We can also express this result by saying that every cube is congruent to 0, 1, or 8 (mod 9).

  Are there any integers a, b, c for which ?