Worlds of David Darling
Encyclopedia of Science
Home > Encyclopedia of Science

prime number

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, ...

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."

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 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. About 6,000 prime numbers are known of which the largest is 213466917-1. 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 'undecideable.' 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. See also Goldbach's conjecture, Ulam spiral, and Ishango bone.

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.

Related categories