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 togethers. 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 (ca 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 one thinks that the gaps may be expanding in a regular pattern, it suddenly drops back down. This means that one cannot predict which numbers are primes. 'The prime numbers appear to be scattered throughout the universe of numbers' (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 has therefore taken 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, one 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, one looks 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. One then continues 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 so the prime numbers thinned out. 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 in the world.

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, noticing his extraordinary mathematical abilities, 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' arrival, mathematics had been seen as a tool for calculation, the workhorse of the other sciences. But, 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 '3-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' 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 3-dimensional landscape is a 3-dimensional graph with x, y and z axes. One is mainly used to 2-dimensional graphs where the x-axis is horizontal across the page and the y-axis is vertical up the page. 3-dimensional graphs have an added z-axis projecting through the page. The Riemann landscape can be envisaged as being like a 3-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.

An unmarried man, he was renowned for his eccentricities and his love of cricket. He abhorred having his photograph taken and 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, and 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, and 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 then enabled Hardy to enjoy the cricket in perfect sunshine. Another example occurred during a trip to Denmark when 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 which amazed him and was to be the start 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 100 million 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.

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.

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 recognized 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 hand to mouth 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.

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⁶.'

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 WWII by two years, and saving countless lives.

After the war, Turing continued to use machines to solve mathematical problems, and built 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 and, 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.8 million 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 our 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 WWII, Princeton had taken over as the world's pre-eminent institution for mathematics and was therefore a mecca for mathematicians.

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 2 to 8 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 2-, 3-, 4-, or 6-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 one makes an on-line financial transaction, one is making use of prime numbers. It is essential that such transactions are secure and so the data 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.