A prime number (or a prime) is a
natural number greater than 1 that has no positive
divisorsother than 1 and itself. A natural number greater than 1 that is not a prime number is called a
composite number. For example, 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2 and 3 in addition to 1 and 6. The
fundamental theorem of arithmetic establishes the central role of primes in
number theory: any integer greater than 1 can be expressed as a product of primes that is unique
up to ordering. This theorem
requires excluding 1 as a prime. The property of being prime is called primality. A simple but slow method of verifying the primality of a given number
n is known as
trial division. It consists of testing whether
n is a multiple of any integer between 2 and √
n. Algorithms that are much more efficient than trial division have been devised to test the primality of large numbers. Particularly fast methods are available for primes of special forms, such as
Mersenne primes. As of 2011, the
largest known prime number has nearly 13 million
decimal digits
There are
infinitely many primes, as
demonstrated by Euclid around 300 BC. There is no known useful formula that yields all of the prime numbers and no composites. However, the distribution of primes, that is to say, the statistical behaviour of primes in the large, can be modeled. The first result in that direction is the
prime number theorem, proven at the end of the 19th century, which says that the
probability that a given, randomly chosen number is prime is inversely
proportional to its number of digits, or the
logarithm of
n.
Many questions around prime numbers remain open, such as
Goldbach's conjecture, which asserts that every even integer greater than 2 can be expressed as the sum of two primes, and the
twin prime conjecture, which says that there are infinitely many pairs of primes whose difference is 2. Such questions spurred the development of various branches of number theory, focusing on
analytic,
algebraic aspects of numbers. Primes are used in several routines in
information technology, such as
public-key cryptography, which makes use of properties such as the difficulty of factoring large numbers into their prime factors. Prime numbers give rise to various generalizations in other mathematical domains, mainly
algebra, such as
prime elements and
prime ideals.
