But in this number system we don’t have unique factorization into e-primes: for example, 2, 6, and 18 are all e-primes, and the e-number 36 can be written as either or .
Example 2 (due to David Hilbert). Consider just the numbers of the form ,
and consider the factorization of h-numbers into smaller h-numbers. We’ll call an h-number h-composite if it can be written as a product of smaller h-numbers, and h-prime if not. So 25 and 45 are h-composite numbers because and , but 9 and 21 are h-prime numbers because they can’t be written as products of smaller h-numbers. The first few h-primes are
But in this number system we don’t have unique factorization into h-primes: for example, 9, 21, and 49 are all h-primes, and the h-number 441 can be written as either or .
However, there are some number systems, other than the positive integers, where we do have unique factorization. We give two examples:
Example 3. Consider the numbers of the form , where a and b are integers (√2-numbers). Such numbers include and , and we can carry out ordinary arithmetic with them, replacing (√2)2 wherever it arises by 2:
In this system we can define √2-prime and √2-composite numbers: for example, is √2-composite, because it can be written as . It is less easy to decide which are the √2-primes, but this can be done, and we can prove that every √2-number can be written as a product of √2-primes in only one way, apart from the order in which they appear.
Example 4. This is similar to the previous example, except that we replace √2 by i, the (imaginary) square root of −1. These numbers of the form , where a and b are integers, were introduced by Gauss in 1801, and are known as Gaussian integers. Such numbers include and , and we can carry out arithmetic with them, replacing i2 wherever it arises by −1: for example,
In this system Gauss defined Gaussian primes and Gaussian composite numbers, and proved that every Gaussian integer can be written as a product of Gaussian primes in just one way, apart from the order in which the Gaussian primes appear.
We can imitate the ideas of Examples 3 and 4 to explore prime and composite numbers of the form , where n is an integer. We’ll assume that n is ‘square-free’—that is, it has no square factors other than 1, because we can simply remove them: for example, because we can replace √18 by √2.
We sometimes have unique factorization into primes, as happened for and , but not always. When n is positive, it is not known in general when there’s factorization into primes in just one way. But when n is negative, we can give a complete answer. As before we don’t always get unique factorization: for example, when , the numbers, , and all play the role of primes, and yet we can write
so the factorization into primes is not unique in this case.
In his Disquisitiones Arithmeticae Gauss showed that there is unique factorization when (the Gaussian integers), and for a few other negative square-free values which he listed. He believed these to be the only ones, and this was eventually confirmed in the 1950s and 1960s by several writers, including Kurt Heegner (whose proof was incomplete), Harold Stark (who provided a complete proof) and Alan Baker (who proved it independently). We conclude this chapter with their remarkable result:
The Baker–Heegner–Stark theorem: For numbers of the form , where n is negative and square-free, factorization into primes is unique if and only if
Chapter 8How to win a million dollars
In 2000 the Clay Mathematics Institute offered a prize of one million US dollars for the solution of each of seven famous problems, widely considered to be among the most important in the subject. The Riemann hypothesis was one of these ‘millennium problems’, and experts have been trying to prove it for more than 150 years.
So what is the Riemann hypothesis, and why is it important? The problem is concerned with the distribution of prime numbers, and was introduced by Bernhard Riemann, a German mathematician who died at the early age of 39 while a professor at Göttingen University, where he had followed in the footsteps of Gauss and Dirichlet. Elected to the Berlin Academy in 1859, Riemann expressed his gratitude by presenting his only paper in number theory, ‘On the number of primes less than a given magnitude’ (see Figure 33). Only nine pages long, it is now regarded as a classic.
33. (a) Bernhard Riemann.
33. (b) Riemann’s 1859 paper.
In very broad terms the Riemann hypothesis asks whether all the solutions of a particular equation have a particular form. This is very vague, and the detailed assertion, which is still unproved, is:
Riemann hypothesis: All the non-trivial zeros of the Riemann zeta function have real part .
But what does this mean, and what is its connection with prime numbers?
Infinite series
To investigate these questions we’ll need to enter the world of infinite series. The series
where the denominators are the powers of 2, continues for ever. What happens when we add all these numbers together? Adding them one number at a time gives
Although we never reach 2 by adding a finite number of terms
