History of Prime Numbers

Prime numbers have been studied for more than two thousand years. Their history runs from early counting practices and Greek geometry through the analytic number theory of the nineteenth century to their present role in public-key cryptography.

Ancient Roots

A prime number is a whole number greater than 1 that has no positive divisors other than 1 and itself. The first numbers meeting this definition are 2, 3, 5, 7, 11 and 13. Every whole number greater than 1 that is not prime is composite, meaning it can be written as a product of smaller factors.

The extent of prime number knowledge in the earliest civilizations is difficult to establish. The Ishango bone, a notched bone artifact from central Africa dated to roughly 20,000 years ago, contains a tally group of 11, 13, 17 and 19, though whether this reflects deliberate selection of primes or coincidence remains disputed among researchers. Clearer evidence appears in Egyptian mathematics. The Rhind Mathematical Papyrus, copied around 1550 BC, presents tables of unit fraction expansions in which numbers with few divisors are handled differently from those with many, which suggests a working awareness that certain numbers resist factoring. Babylonian scribes compiled reciprocal tables that similarly distinguish between numbers that divide the base 60 evenly and those that do not.

Greek Mathematics

The systematic study of primes began in ancient Greece. The Pythagoreans of the sixth century BC studied divisibility and numbers regarded as perfect. By the time of Euclid, around 300 BC, primes were treated as a distinct category worthy of formal proof. Later Greek writers developed the explicit classification of numbers as perfect, abundant or deficient; it features prominently in Nicomachus's Introduction to Arithmetic around AD 100.

Books VII through IX of Euclid's Elements contain the foundational results. Proposition 20 of Book IX establishes that no finite list of primes can be complete, which is the standard proof that infinitely many primes exist. Euclid also proved the result now called Euclid's lemma, from which the Fundamental Theorem of Arithmetic follows: every whole number greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors. This theorem is the reason primes are described as the building blocks of arithmetic. A further result of Book IX links even perfect numbers to primes of a particular form, a connection later completed by Euler.

Around 240 BC, Eratosthenes of Cyrene devised a procedure for listing all primes below a chosen limit by repeatedly striking out the multiples of each prime found. The method is described in the writings of Nicomachus and remains in practical use as a computer algorithm.

Medieval Developments

Progress in Europe slowed considerably after the classical period, but work continued elsewhere. Mathematicians of the Islamic world extended Greek results and produced new ones. In the eleventh century, Ibn al-Haytham stated the criterion now known as Wilson's theorem, which characterizes primes through factorials, though a proof was not published until Lagrange supplied one in 1771. Thabit ibn Qurra had earlier established a rule for generating amicable pairs that depends on producing primes of a specific form. In thirteenth century Italy, Leonardo of Pisa, known as Fibonacci, described trial division by primes up to the square root of a candidate as a practical test.

The Early Modern Period

Interest revived sharply in seventeenth century Europe. Pierre de Fermat corresponded widely on number theory and stated in 1640 the result called Fermat's little theorem, which underlies most modern primality tests. He also examined numbers of the form 2²ⁿ + 1 and conjectured that all are prime, a claim Euler disproved in 1732 by factoring the fifth such number.

Marin Mersenne, a French friar and correspondent of Fermat and Descartes, studied numbers of the form 2^p - 1. In 1644 he published a list of exponents he believed produced primes. The list contained several errors, but the class of numbers has carried his name ever since, and Mersenne primes remain the source of nearly every record for the largest known prime.

Key Historical Milestones

• Euclid (c. 300 BC): Proved in his Elements that there are infinitely many primes and established the basis of the Fundamental Theorem of Arithmetic.
• Eratosthenes (c. 240 BC): Devised the Sieve of Eratosthenes for finding all primes up to a specified limit.
• Marin Mersenne (17th century): Studied primes of the form 2^p - 1, now called Mersenne primes.
• Leonhard Euler (18th century): Connected the primes to analysis through his product formula of 1737 and proved that the sum of the reciprocals of the primes diverges.
• Carl Friedrich Gauss and Adrien-Marie Legendre (c. 1800): Independently conjectured the Prime Number Theorem describing how primes thin out among the integers.
• Bernhard Riemann (1859): Related the distribution of primes to the zeros of the zeta function, producing the Riemann hypothesis.

Analytic Number Theory

The nineteenth century transformed the subject by applying methods of calculus to questions about whole numbers. Peter Gustav Lejeune Dirichlet proved in 1837 that any arithmetic progression whose first term and common difference share no common factor contains infinitely many primes. Pafnuty Chebyshev obtained the first rigorous bounds on the counting function in the 1850s and proved Bertrand's postulate, which guarantees a prime between any number and its double.

Riemann's memoir of 1859 introduced the analytic tools that eventually settled the central question. In 1896 Jacques Hadamard and Charles Jean de la Vallée Poussin independently proved the Prime Number Theorem, showing that the number of primes below a value n is asymptotic to n / ln(n). The claim is about the ratio of the two quantities, which tends to 1; their difference grows without limit, which is why more refined estimates are used in practice. An elementary proof avoiding complex analysis was found by Atle Selberg and Paul Erdős in 1949.

Computation and Cryptography

Mechanical and then electronic computation changed what could be verified. Édouard Lucas proved in 1876 by hand that 2¹²⁷ - 1 is prime, a record that stood for 75 years. The SWAC computer found several new Mersenne primes in 1952, and the Great Internet Mersenne Prime Search, founded in 1996, has since distributed the work across volunteer machines. Record primes now run to tens of millions of digits. In 2002, Manindra Agrawal, Neeraj Kayal and Nitin Saxena published the AKS algorithm, the first method proven to test primality in polynomial time without unproved assumptions.

The practical importance of primes grew from a simple asymmetry: multiplying two large primes is fast, while recovering them from the product is not. Whitfield Diffie and Martin Hellman published a key exchange method based on related ideas in 1976, and Ron Rivest, Adi Shamir and Leonard Adleman introduced the RSA cryptosystem in 1977. Equivalent methods had been discovered earlier at the British agency GCHQ, where James Ellis set out the concept of non-secret encryption in 1969, Clifford Cocks worked out an equivalent of RSA in 1973 and Malcolm Williamson an equivalent key exchange in 1974. That work stayed classified until 1997. These systems secure much of the traffic on the internet today, although the prospect of large-scale quantum computers has prompted work on replacement schemes based on other mathematical problems.

Open Questions

Several basic questions about primes remain unresolved. The Riemann hypothesis, one of the Millennium Prize Problems, concerns the location of the zeros of the zeta function and would sharpen estimates of prime distribution. Goldbach's conjecture of 1742, that every even number greater than 2 is a sum of two primes, has been checked far into the range of computation but not proved. The twin prime conjecture, that infinitely many pairs of primes differ by 2, saw a major advance in 2013 when Yitang Zhang proved that infinitely many pairs differ by at most a fixed bound, a figure later reduced to 246 through collaborative work.

Explore More Prime Number Topics

Try our Prime Number Check, or read about what prime numbers are, how to check whether a number is prime, and the Sieve of Eratosthenes.