An integer greater than one is called a
prime number if its only positive divisors (factors) are one and
itself. For example, the prime divisors of 10 are 2 and 5; and the first six
primes are 2, 3, 5, 7, 11 and 13 (the first
10,000, and other lists are available). The Fundamental Theorem of
Arithmetic shows 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.
The uses of primes are manifold. They were first studied because
many of the properties of numbers are directly tied to their factorizations.
Beside their austere intrinsic beauty, prime numbers are now key to the
Internet revolution because they are used for a variety of encryption
methods used to keep transactions safe. NASA scientists even decided
that they are a good sign of intelligence and have included a short list
of primes on the plaques sent out with the voyager spacecraft. This
interest is not new. Over 200 years ago, Carl Friedrich Gauss (one
of the greatest mathematicians of all time) 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. (Carl Friedrich Gauss, Disquisitiones
The ancient Greeks proved (ca 300 BC) that there were infinitely many
primes and that they were irregularly spaced (there can be arbitrarily large
gaps between successive primes). On the other
hand, in the nineteenth century it was shown that the number of primes less than
or equal to n approaches n/log n) (as n gets very
large); so a rough estimate for the nth prime
is n log n (see the document "How many
primes are there?")
The Sieve of Eratosthenes is still the one of the most
efficient way of finding all very small primes (e.g., those less than say
1,000,000,000,000). However, most of the largest primes are found using special cases of
Lagrange's Theorem from group theory. See the separate documents on proving primality for more information.
In 1984 Samuel Yates defined a titanic prime to be any prime with
at least 1,000 digits [Yates85].
When he introduced this term there were only 110 such primes known; now there are
over 1000 times that many! And as computers and cryptology continually give
new emphasis to search for ever larger primes, this number will continue to
grow. Before long
we expect to see the first ten million digit prime.
There is so much more to be said! Why not spend a few moments perusing
this site or spend a quiet evening with one of the excellent texts in our reference pages.