Prime numbers are part of the set of ordinary numbers known as integers, but which are divisible only by the number itself and by 1. They thus have exactly two positive integer factors.

Here are the first seventeen prime numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59

Note that 1 is not a prime number as it only has one factor, 1 itself.

The number 9 is not a prime number because it can be divided evenly by 1, 3 and 9. Such a number is called a composite number. It can be shown that all composite numbers can be produced by multiplying prime numbers together. For this reason, prime numbers are often called the building blocks of mathematics, analogous to the atoms of chemistry or cells of biology.

The number 2 is interesting in that it is the only prime number that is even. In the words of an American professor of mathematics, '2 is odd because it's even'.

Another way of describing a prime number is that it is a positive integer that is itself not the product of two smaller positive integers.

History of Primes

Euclid

Man has been interested in prime numbers for thousands of years, and the ancient Greeks were the first people to try to understand them. Euclid proved (circa 300 BC) that there are an infinite number of primes and that they are irregularly spaced, that is the size of the gaps between successive prime numbers seems very arbitrary. Thus, looking at the first few prime numbers given in the list above, the gaps are:

1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6

Just when you might think that the gaps may be expanding in a regular pattern, they suddenly drop back down. This means that it is impossible to predict which numbers are primes. 'The prime numbers appear to be scattered throughout the universe of numbers', explains Prof Marcus du Sautoy)¹. This has been likened to trying to predict the arrival times of buses during the rush hour. This is extremely frustrating to the mathematician who fundamentally wants to find patterns and therefore make sense out of numbers.

Sieve of Eratosthenes

It is, however, possible to identify which numbers in a list are primes. Eratosthenes was a Greek mathematician who lived from 276 BC to 194 BC in Northern Africa. He is credited with the invention of a method of finding prime numbers described here, and which therefore carries his name.

In this method, all the numbers of interest are written sequentially into a grid², often called a number square. So to find the primes up to 100, you would use a 10 x 10 number grid. Then, beginning with the first prime, 2, all 'proper' multiples of 2 - that is, multiples other than 2 itself - are crossed out. Thus, for example, the numbers 4, 6, 8, etc are crossed out. Once this has been completed, you look to the beginning of the grid and the next number not already crossed out - in this case 3 - will be prime. The number 3 is left untouched but all proper multiples of 3 are crossed out. You then continue to cross out all the proper multiples of each successive (prime) number.

Since this table is square, when you have finished crossing off all the proper multiples of the primes in the first row, the table will contain only primes.

For very large numbers, Eratosthenes's sieve is not very efficient and more elaborate methods are required, such as the use of Lagrange's Theorem from group theory.

Carl Friedrich Gauss (1777 - 1855)

Gauss was a German mathematician and physicist who became famous when, in 1801, he published his Disquisitiones Arithmeticae, a masterpiece of mathematical reasoning and logic.

The gauss, an SI-related unit of magnetism (also called 'magnetic flux density'), is named after him (1G = 10^-4 tesla). Indeed, Gauss is often referred to as the 'Prince of Mathematicians' due to the quality and range of his mathematical interests.

Gauss was very much a child prodigy. He said that he could compute before he could read and that, at the age of three, he had been correcting his father's arithmetic. As a schoolboy, he kept a secret diary-cum-notebook of his mathematical discoveries.

It was in 1801 at the age of 24 that he really 'became a star' when was able to help astronomers who had 'lost' a newly-discovered planet Ceres, due to the glare from the sun. Gauss was able to find a mathematical pattern in its flight path and suggested to astronomers where in the night sky they might look again. Sure enough, there it was!

However, on his 15th birthday, Gauss had been given a present which was to change the course of mathematical history. It was a book of logarithms, at the back of which was a table of prime numbers. Gauss was obsessed by this list and spent hours poring over the numbers trying to find some pattern or regularity and, to start with, he confirmed the findings of the ancient Greeks that there appeared to be no pattern. However, in an application of lateral thinking, in contrast to the Greeks who had asked, 'How can we predict which numbers are prime', he asked, 'How many prime numbers are there?'. He discovered that if he grouped the numbers according to powers of 10 (that is: 1-10, 1-100, 1-1000 etc) and then picks a number at random from within each range, the probability of it being prime is as shown in the table:

In this way a 'regularity appeared out of the mist of disorder'. Each time he added a '0', the probability of getting a prime number went down by the same amount. That is, as the numbers got bigger, the prime numbers thinned out according to a predictable pattern. By plotting a graph of inverse probability against number, he obtained a curve which exhibited a beautiful regularity. For the first time ever, a pattern had been observed in the occurrence of prime numbers along the number line. Gauss realised that this graph only provided a rough estimate of the number of primes and so kept this discovery a secret until much later in his life. This was for two reasons; firstly he was employed as an astronomer, mathematics was just his hobby. Secondly, he was reluctant to publish unless he was sure of the perfection of his work. Furthermore, although Gauss could see the pattern in the primes, he was unable to prove his conjecture and, for a mathematician, proof is everything. Nevertheless, the presence of Gauss had transformed the sleepy university town of Göttingen into a mathematical Mecca.

Bernhard Riemann (1826 - 1866)

Among Gauss's disciples at the University of Göttingen was the person destined to make the next major advance in our understanding of prime numbers. This was Bernhard Riemann.

Riemann was born in 1826 in the kingdom of Hannover, later to become part of Germany. His father was a Lutheran minister. Riemann showed an interest in mathematics and history at an early age. At 16 years of age, he transferred to the gymnasium school at Lüneburg, where the Director, Schmalfuss, noticed his extraordinary mathematical abilities, and gave him the freedom of his library and its fine collection of mathematical works. It was here that Riemann first became aware of the 'problem of the primes' when, it is said, he read an entire 859-page book by Legendre³ on number theory in six days, after which he returned it saying, 'This is a wonderful book; I know it by heart'.

Some years later, in 1849, Riemann came to study at Göttingen University, attracted by the presence of Gauss. Prior to Gauss's arrival, mathematics had been seen as a tool for calculation, the workhorse of the other sciences. However, in Germany, this notion had been transformed as mathematicians dealt with increasingly abstract concepts. Indeed, Riemann's PhD was to be on the geometric properties of complex variables (algebraic geometry⁴).

At Göttingen, Riemann 'picked up the baton' from Gauss, one of whose interests was Euler's 'zeta function'. Riemann realised that he could use the zeta function to build a 'three-dimensional landscape of numbers' which at a later date he was able to use to give an exact solution to the number of primes in Gauss's average curve of the 'prime number staircase'. Thus, if one plots how many primes exist below a certain given number (say, below 10, 100, 1,000, 10,000 etc), one obtains a smooth curve with small wiggles (deviations).

The three-dimensional landscape is a three-dimensional graph with x, y and z axes. Most people are used to two-dimensional graphs where the x-axis is horizontal across the page and the y-axis is vertical up the page. Three-dimensional graphs have an added z-axis projecting through the page. The Riemann landscape can be envisaged as being like a three-dimensional mountain-scape model on a table based on these axes, where the z axis is the elevation. It has peaks and valleys. The points at which the mountains' bases are at table level, ie z=0, are known as the 'Riemann zeros'. Riemann also discovered something quite unexpected: the 'zeros' all seem to be in a straight line; that is, have the same value of 'x'. This is called the 'critical line'.

According to Professor Sir Michael Berry, FRS of Bristol University, the Riemann zeros correspond to the many different frequencies that make up a sound wave. They are 'harmonies in the music of the primes.'

Riemann worked out that if the zeros really do lie on the critical line, then the primes stray from Gauss's distribution exactly as much as a bunch of coin tosses stray from the 50:50 distribution law. This is a startling conclusion. The primes aren't just unpredictable, they really do behave as if each prime number is picked at random, with a calculable probability - almost as though they were chosen with a weighted coin.

Riemann thought that, as so many of his calculated 'zeros' lay on the critical line, in all probability all of them would. The problem was that he was unable to prove it.

This behaviour of the prime numbers has come to be known as 'The Riemann Hypothesis' and is one of the most famous and important unsolved problems in mathematics⁵, having attracted the attentions of some of the most celebrated mathematicians in the world. It has been said that this was as revolutionary to mathematics as Einstein's E = mc² was to physics.

GH Hardy (1877 - 1947)

At the start of the 20th Century, England was rather a mathematical backwater, but GH Hardy was about to change all this. He had been obsessed by prime numbers all his life and had once commented that 'Tables of primes are better than football reports for light breakfast table reading'.

As explained earlier, Riemann had observed that there were so many zeros on the critical line that it was probable that all of them are. However, he had been unable to prove it. Early in his career Hardy had shown that there were infinitely many zeros on the line. At first glance this might sound as though he had solved the Riemann Hypothesis. However, the problem was that if there were an infinite number of zeros on the line there could equally be an infinite number of zeros off the line. Proof of the Riemann Hypothesis was still proving to be remarkably elusive.

From 1931, Hardy occupied the Sadlerian Chair of Mathematics in Cambridge, which he considered to be the foremost mathematics chair in the country.

An unmarried man, he was renowned for his eccentricities and his love of cricket. He abhorred having his photograph taken; only five snapshots of him are known to exist. Later in his life he came to hate mirrors because he didn't like to watch himself growing old, so his first action on entering any hotel room was to cover any mirror with a towel. Hardy always claimed to be a disbeliever in God, but amused himself by trying to fool God by playing 'mind games' with him. For example, when he attended cricket matches he would take what he called his 'anti-God battery', consisting of thick sweaters, an umbrella, mathematical papers to read and/or referee and student examination scripts to mark. His reasoning was that, if God existed then He would think that Hardy hoped rain would come so that he could then get on with his work. Hardy then thought that God would have the sun shine all day to spite him. This ostensibly enabled Hardy to enjoy the cricket in perfect sunshine. Another example occurred when Hardy was on a trip to Denmark; a colleague was astounded to receive a postcard from Hardy claiming that he had proved the Riemann hypothesis. Hardy later explained that, if God existed, then He would not allow the boat to sink on the return journey and give him the same fame that Fermat had achieved with his 'last theorem'.

Hardy's mathematical interests covered a wide range - Diophantine analysis, summation of divergent series, Fourier series, the Riemann zeta function and the distribution of primes.

Hardy had, in 1911, commenced what turned out to be a long and fruitful collaboration with JE Littlewood - a collaboration which was to last 35 years. Then in early 1913, he received a letter from Srinivasa Ramanujan that amazed him and was to be the start of the second major collaboration in his life. In his letter, Ramanujan claimed to have discovered a formula that calculated the number of primes up to 100million with no error. Hardy very quickly recognised that the letter had been written by a mathematical genius, and invited Ramanujan to Cambridge. Between them they were to write five remarkable papers over their five years of collaboration.

Srinivasa Ramanujan (1887 - 1920)

Srinivasa Ramanujan was a trained, but amateur and unknown, mathematician working as a clerk in the accounts section of the Madras Port Trust.

In his letter of application for this post, Ramanujan had written,

I have passed the Matriculation Examination and studied up to the First Arts but was prevented from pursuing my studies further owing to several untoward circumstances. I have, however, been devoting all my time to Mathematics and developing the subject.

Despite his lack of a university education, Ramanujan was clearly well known to the university mathematicians in Madras for, with his letter of application, Ramanujan included a reference from EW Middlemast, Professor of Mathematics at The Presidency College in Madras, who wrote:

I can strongly recommend the applicant. He is a young man of quite exceptional capacity in mathematics and especially in work relating to numbers. He has a natural aptitude for computation and is very quick at figure work.

During the period 1912 - 1913, Ramanujan sent samples of his theorems to three academics at the University of Cambridge, UK. In his letters of introduction, Ramanujan had written:

I have had no university education but I have undergone the ordinary school course. After leaving school I have been employing the spare time at my disposal to work at mathematics. I have not trodden through the conventional regular course which is followed in a university course, but I am striking out a new path for myself. I have made a special investigation of divergent series in general and the results I get are termed by the local mathematicians as 'startling'.

Hardy, alone of these academics, studied and recognised the brilliance of Ramanujan's work, recognising that Ramanujan had independently and unknowingly discovered, and therefore corroborated, the work of Gauss, Riemann and others. Hardy invited Ramanujan to study under him at Cambridge, where he arrived in 1914, just before the outbreak of World War I. There then followed a period of extraordinary productivity.

Like Hardy, Ramanujan was obsessed by prime numbers and had spent hours of his life filling up notebooks with his ideas. He was largely self-taught and there are stories that his wife had to feed him by hand as he worked on his theories. Living as he had done in India, one of his great strengths was his mathematical naiveté, being completely untarnished by Western ideas and dogma. Ramanujan claimed that many of his ideas were given to him in his dreams by the family goddess, Namagiri.

Ramanujan fell seriously ill of tuberculosis in 1917 and his doctors feared that he would die.

Hardy, always somewhat inept at light conversation, tells the following story about an occasion when he visited Ramanujan in hospital:

Once, in a taxi from London, I noticed its number, 1729. When I entered the room I mentioned this to Ramanujan, saying that it was 'rather a dull number' and that I 'hoped that wasn't a bad omen'. 'Not at all, Hardy' he replied. 'It's a very interesting number. It is the smallest number expressible as the sum of two cubes in two different ways⁶.'

Ramanujan knew this simply because of his love of numbers. All through his life, he had experimented with numbers and, as a child, he probably found prime numbers into the many thousands, trying to find a pattern that other people had missed. Though 1729 is not a prime, he nonetheless was familiar with its properties.

On 18 February, 1918 Ramanujan was elected a fellow of the Cambridge Philosophical Society and then three days later his name appeared on the list for election as a Fellow of the Royal Society of London (FRS). His election as a Fellow of the Royal Society was confirmed on 2 May, 1918.

Despite all this success, Ramanujan suffered from depression, not least because he was unable to maintain proper correspondence with his wife in India. Hardy suggested therefore that Ramanujan should return to India and Ramanujan sailed on 27 February, 1919 arriving on 13 March. However his health was very poor and, despite medical treatment, he died there the following year.

Alan Turing (1912 - 1954)

Considered by many to be the founding father of artificial intelligence and computer science, Alan Turing is best known for the key role he played in the development of a device which decoded messages encrypted on the German 'Enigma' machine. What is less well known is the role the Riemann Hypothesis played in helping him to achieve this.

Turing graduated in mathematics from Cambridge in 1934.

During World War II, Turing was one of a group of mathematics specialists sent to Bletchley Park to intercept and decode German messages. During quiet moments, Turing's mind would turn to the problem he'd been working on in Cambridge before the outbreak of war, namely the Riemann Hypothesis. Turing had started with the premise that the Riemann Hypothesis might be wrong and had designed a machine with cogwheels to sum a Fourier series for the Riemann zeta-function. This machine had been partly inspired by a tide-predicting machine in Liverpool. He set the machine to search for zeros off the critical line.

Although Turing had not completed his Riemann machine at Cambridge, the work he'd done there helped him build a machine to crack the German codes instead, once he'd been posted to Bletchley Park. His machine was wildly successful and is credited with shortening World War II by two years and saving countless lives.

After the war, Turing continued to use machines to solve mathematical problems, building the prototype of the modern computer. Using this, he managed to locate the first 1,104 zeros, which all lay on the critical line, before the machine broke down. By 1952, a computer had been built which discovered the first prime numbers beyond the computational abilities of the human mind. Today, the largest identified prime number found, discovered in 2006, has over 9.8million digits. This number is absolutely colossal - beyond superlative. For example, one of the largest units that scientists are used to handling is Avogadro's Constant - the number of atoms in one mole of substance, for example in 12g of ¹²C. This is 6.023 x 10²³, and is approximately equal to the number of grains of sand on Earth. Only 80 digits are required to express the total number of atoms in the universe⁷!

Hugh Montgomery

The next major advance in human understanding of the prime numbers came as the result of a chance meeting over tea between Hugh Montgomery⁸ and Freeman Dyson⁹ at the Institute for Advanced Study, Princeton. Since World War II, Princeton had taken over as the world's pre-eminent institution for mathematics and was therefore a mecca for mathematicians.

Montgomery explained to Dyson that he'd been looking at the zeros of the zeta function and described the formula he had found for this distribution, which showed that the zeros have a particularly aesthetic spacing. Dyson immediately recognised this as being similar to the spacing of the energy levels in the nucleus of the uranium atom, saying something like, 'Well, that's the density of the pair correlation of eigenvalues of random matrices in the Gaussian Unitary Ensemble.'

Dyson had recognised a connection between two apparently unconnected fields of knowledge - quantum physics and number theory. It turned out that physicists looking for ways to characterise the behaviour of atomic particles had produced a formula that was very similar to Montgomery's description of the zeros of the Riemann zeta function.

From this serendipitous meeting between Dyson and Montgomery has emerged a whole new approach to examining the Riemann Hypothesis. There is the intriguing possibility that the quantum universe behaves as if it is driven by the location of the Riemann zeta function zeros.

'We have all this evidence that the Riemann zeros are vibrations, but we don't know what's doing the vibrating.' - M du Sautoy, The Music of the Primes

Biological Significance of Prime Numbers

Cicadas are a large group of flying, plant-eating insects related to the plant bugs. They are common in warm countries and are well-known for the chirping noise made by the males. Most cicada species have life cycles that span two to eight years, spending most of their lives underground before emerging as adults.

In a few species, however, almost all the individuals in a given location come out of hiding at the same time. These species are known as 'periodic cicadas', and they generally belong to the genus Magicicada. Periodic cicadas usually have 13- or 17-year life cycles. Their development is so synchronised that practically no adults are present in the 12 or 16 years between emergences. When these cicadas do come out of their underground homes, they appear in huge numbers and create a cacophony of sound as they indulge in a frenetic - if brief - mating orgy.

Interestingly, both 13 and 17 are prime numbers, and mathematicians were curious to understand whether this was just coincidental or due to some form of evolutionary pressure.

It turns out that prime number life cycles enable periodic cicadas to evade predation by creatures with shorter life cycles. For example, consider a cicada with a 12-year life cycle. All predators with two-, three-, four-, or six-year cycles would get an opportunity to prey on them, potentially wiping out an entire population. With prime-number life cycles, the chances of predator and prey coinciding would be much reduced.

A Modern Application: e-commerce

Every time you make an online financial transaction, you are making use of prime numbers. It is essential that such transactions are secure, so the data being transferred is encrypted. The most popular type of public-key encryption was invented by Ronald L Rivest of the Massachusetts Institute of Technology, Adi Shamir of the Weizmann Institute of Science in Rehovot, Israel, and Leonard M Adleman of the University of Southern California in Los Angeles, and is therefore known as the RSA cryptosystem.

The security of this system capitalises on the difficulty of factorising a large number into its prime building blocks. Thus, the RSA system involves a secret key consisting of two prime numbers that are multiplied together to create the lengthier public key. The process of factoring a large number to determine its prime-number components presents a formidable computational challenge. Indeed, it is virtually impossible!

A proof of the Riemann Hypothesis should give us new insight into the behaviour of prime numbers, perhaps even enough to enable us to factorise large numbers into their prime building blocks. This increased understanding could possibly cause the collapse of the online commercial world as we know it.