## prime numberAn integer greater than 1 that is divisible only by 1 and itself. 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 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, ... 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 2^{13466917}-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• PRIME NUMBERS• TYPES OF NUMBER | |||||

Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact |