prime number

sieve of Eratosthenes

Figure 1. The sieve of Eratosthenes.

Explanation of Sieve of Eratosthenes

Figure 2. An explanation of the sieve of Eratosthenes.

Prime numbers that have a starred pattern, similar to the one frequently used to denote 5, can always be expressed as the sum of two square numbers

Figure 3. Prime numbers that have a starred pattern, similar to the one frequently used to denote 5, can always be expressed as the sum of two square numbers.

A prime number is an integer greater than 1 that is divisible only by 1 and itself. The prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ... Another way to think of them is as numbers that are not rectangular numbers (i.e. numbers that can be arranged in a rectangular form.


Sieve of Eratosthenes

Eratosthenes, a Greek mathematician and a friend of Archimedes, devised a method for obtaining prime numbers in their numerical order. This method is known as the sieve of Eratosthenes. Figure 1 shows the principles on which it works.


Look at the drawing of the sieve. Imagine that all the numbers from 1 to 25 are being dropped through the sieve. All these numbers drop through the top rack, but on on the second those which are multiples of 2 are caught. These are colored green.


On the third rack all the numbers which are multiples of 3 are caught, except of course, those which have already been caught as multiples of two. These are colored yellow. In the fourth rack 25 is caught - this is the only multiple of 5 which is neither a multiple of 3 nor a multiple of 2. It is colored orange.


The final numbers that get through to the final rack are prime numbers (see Figure 2).


You will see that there are black squares on the sieve. In the third rack these show where the multiples of 3 would have been caught if they had not been caught by the rack above. The black squares in the fourth rack show where the multiples of 5 would have been caught had they not been caught by the two racks above.


You may wonder why there is no rack taking out multiples of 4. This is because 4 is a multiple of 2, and therefore all multiples of 4 are also multiples of 2.


Formulae for primes

This 'sieve' method of producing prime numbers is laborious, and mathematicians have long been searching for a simple method of producing them, without success.


The expression n2 - n + 41 might appear to be a possible formula for prime numbers.


When n = 1 the expression = 41 which is prime
When n = 2 the expression = 43 which is prime
When n = 3 the expression = 47 which is prime
When n = 4 the expression = 53 which is prime
and so on. But it breaks down when n = 41. Can you see why?


Fermat, a seventeenth-century mathematician, thought that he had found a formula for prime numbers: 22^n + 1.

When n = 1 the expression = 5(22 + 1)
When n = 2 the expression = 17(24 + 1)
When n = 3 the expression = 257(28 + 1)
When n = 4 the expression = 65,537(216 + 1)
When n = 5 the expression = 4,294,967,297(232 + 1)


However, Euler, showed that the last number is not prime but is, in fact, 641 x 6,700,417.


Largest prime known

It takes a long time to decide whether any number is prime, and to date, the largest one known is 257,885,161 - 1 which, when worked out has 17,425,170 digits. The testing was done on a computer.


Number of primes

One may wonder whether the primes go on for ever or whether there is in fact one number which is the largest prime number. Euclid, by a very neat argument, proved that there are an unlimited number of primes.


Suppose, he said, that the largest prime number you have found is p. Multiply all the previous prime numbers including p together and add 1. If the result is a prime number, it is naturally, a larger prime than p. If not, it must have divisors none of which can be one of the original primes since they all leave a remainder 1 on division. The divisors of the new number, then, must be prime numbers greater than p. So in either case there is a prime number greater than p, and this process can be continued forever.


The distribution of primes

Prime numbers have fascinated mathematicians for centuries, in large part because of how they are distributed: at first sight, they seem to occur randomly, and yet, on closer inspection, they reveal a subtle order or pattern, that seems to hold deep truths about the nature of mathematics and of the world in which we live. The German-born American mathematician Don Zagier (1951–), in his inaugural lecture at Bonn University, put it this way:


"There are two facts about the distribution of prime numbers which I hope to convince you... The first is that despite their simple definition and role as the building blocks of the natural numbers, the prime numbers ... grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision."


Properties of primes

Prime numbers have many interesting properties. For instance, those which have a starred pattern, similar to the one frequently used to denote 5, can always be expressed as the sum of two square numbers.


The fundamental theorem of arithmetic declares that the primes are the building blocks of the positive integers: every positive integer is a product of prime numbers in one and only one way, except for the order of the factors. This is the key to their importance: the prime factors of an integer determines its properties. The ancient Greeks proved (c. 300 BC) that there are infinitely many primes and that they are irregularly spaced; in fact, there can be arbitrarily large gaps between successive primes. On the other hand, in the 19th century it was shown that the number of primes less than or equal to n approaches n/log n, as n gets very large (a result known as the prime number theorem), so that a rough estimate for the nth prime is n log n. In his Disquisitiones Arithmeticae (1801), Carl Gauss wrote:


"The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated."


The earliest known primality test, as discussed earlier, is the sieve of Eratosthenes, which dates from around 240 BC. However, the use of high-speed computers and of fast algorithms are needed to identify large primes. New record-breaking primes tend to be of the variety known as Mersenne primes, since these are the easiest to find. Much remains unknown about the primes. As Martin Gardner said:


"No branch of number theory is more saturated with mystery ... Some problems concerning primes are so simple that a child can understand them and yet so deep and far from solved that many mathematicians now suspect they have no solution. Perhaps they are 'undecidable.' Perhaps number theory, like quantum mechanics, has its own uncertainty principle that makes it necessary, in certain areas, to abandon exactness for probabilistic formulations."


One of the greatest unsolved problems in mathematics, the Riemann hypothesis, the distribution of prime numbers. There are also some very simple properties of prime numbers which have not yet been proved. A famous example, known as Goldbach's conjecture, is that any number can be expressed as the sum of two primes:


12 = 5 + 7
20 = 17 + 3
34 = 17 + 17 and so on


Nobody has, so far, been able to find out why this should be so, and yet no one has found an even number which cannot be split into two primes.


It has also been proposed that there are an infinite number of so-called prime pairs which are prime numbers differing by two. (11, 13), (29, 31) are cases, but again, no one has yet to establish whether this is so.


See also Ulam spiral, and Ishango bone.


Circular prime

A circular prime is a prime number that remains prime on any cyclic rotation of its digits. An example (in the decimal system) is 1193 because 1931, 9311, and 3119 are also prime. Any one-digit prime is circular by default. In base ten, any circular prime with two or more digits can only contain the digits 1, 3, 7 and 9; otherwise when 0, 2, 4, 5, 6, or 8 is rotated into the units place, the result will be divisible by 2 or 5. The only circular primes known, if we list by just the smallest representative from each cycle, are:


2, 3, 5, 7, 11, 13, 17, 37, 79, 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933, R19, R23, R317, R1031 and possibly R49081.


These last five are the known repunit primes and probable primes. It is conjectured that there are infinitely many repunit primes, so there should be infinitely many circular primes. But it is highly likely that all circular primes not on the list above are repunits.


Primes and the hunt for alien intelligence

In 1941, James Jeans pointed out that the attention of intelligent Martians "if any such there be" could be attracted by using powerful searchlights to flash, in sequence, the first prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, ... Likewise, it has been suggested that the occurrence of sequences of prime numbers in an extraterrestrial radio signal would immediately imply an artificial and intelligent origin. The reception of such a signal occurs in the novel (and film) Contact. Prime numbers were also used in the construction of Drake's cryptogram and the Arecibo message.