Prime numbers

A prime is a positive integer greater than 1 divisible without remainder only by 1 and itself. Thus 2, 3, 5 and 7 are prime, while 1 is neither prime nor composite. The number 2 is the only even prime; every other even integer greater than 2 has 2 as a proper divisor. Integers greater than 1 that are not prime are composite. The fundamental theorem of arithmetic says that each such integer can be written as a product of primes in one unique way, apart from rearranging the factors. For example, 84 = 2 × 2 × 3 × 7.

Euclid's Elements, written in ancient Greece, includes an argument that no finite list can contain every prime. In a modern version of the proof, suppose a list contains primes p₁ through pₙ. Multiply them together and add 1. The resulting number leaves remainder 1 when divided by any prime on the list. It is either prime itself or has a prime divisor absent from the list. Either possibility contradicts the claim that the list contained them all, so there must be infinitely many primes.

The gaps between successive primes do not follow a simple repeating pattern, but the overall density of primes can be estimated. If π(x) denotes the number of primes no greater than x, the prime number theorem states that, for large x, π(x) is approximately x divided by the natural logarithm of x. The estimate describes the long-run distribution; it does not specify where any particular next prime will occur. The theorem was proved independently by Jacques Hadamard and Charles de la Vallée Poussin in 1896.

Prime numbers are important in number theory and have practical uses in computing. RSA, for example, is an integer-factorization cryptographic system: its key-generation procedures involve prime factors, and standards for RSA key establishment are set out by the U.S. National Institute of Standards and Technology. This is one application of primes rather than a property of every encryption method; cryptographic security depends on the complete scheme, its parameters and its implementation.