section_path: History
section_name: History
paragraph_text: History
  
  The Rhind Mathematical Papyrus, from around 1550 BC, has Egyptian fraction expansions of different forms for prime and composite numbers. However, the earliest surviving records of the study of prime numbers come from the ancient Greek mathematians, who called them prōtos arithmòs (πρῶτος ἀριθμὸς). Euclid 's Elements (c. 300 BC) proves the infinitude of primes and the fundamental theorem of arithmetic, and shows how to construct a perfect number from a Mersenne prime. Another Greek invention, the Sieve of Eratosthenes, is still used to construct lists of primes.
  
  Around 1000 AD, the Islamic mathematician Ibn al-Haytham (Alhazen) found Wilson's theorem, characterizing the prime numbers as the numbers n {\displaystyle n} that evenly divide (n − 1) ! + 1 {\displaystyle (n-1)!+1}. He also conjectured that all even perfect numbers come from Euclid's construction using Mersenne primes, but was unable to prove it. Another Islamic mathematician, Ibn al-Banna' al-Marrakushi, observed that the sieve of Eratosthenes can be sped up by considering only the prime divisors up to the square root of the upper limit. Fibonacci took the innovations from Islamic mathematics to Europe. His book Liber Abaci (1202) was the first to describe trial division for testing primality, again using divisors only up to the square root.
  
  In 1640 Pierre de Fermat stated (without proof) Fermat's little theorem (later proved by Leibniz and Euler). Fermat also investigated the primality of the Fermat numbers 2 2 n + 1 {\displaystyle 2^{2^{n}}+1}, and Marin Mersenne studied the Mersenne primes, prime numbers of the form 2 p − 1 {\displaystyle 2^{p}-1} with p {\displaystyle p} itself a prime. Christian Goldbach formulated Goldbach's conjecture, that every even number is the sum of two primes, in a 1742 letter to Euler. Euler proved Alhazen's conjecture (now the Euclid–Euler theorem) that all even perfect numbers can be constructed from Mersenne primes. He introduced methods from mathematical analysis to this area in his proofs of the infinitude of the primes and the divergence of the sum of the reciprocals of the primes 1 2 + 1 3 + 1 5 + 1 7 + 1 11 + ⋯ {\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots }. At the start of the 19th century, Legendre and Gauss conjectured that as x {\displaystyle x} tends to infinity, the number of primes up to x {\displaystyle x} is asymptotic to x / log x {\displaystyle x/\log x}, where log x {\displaystyle \log x} is the natural logarithm of x {\displaystyle x}. A weaker consequence of this high density of primes was Bertrand's postulate, that for every n > 1 {\displaystyle n>1} there is a prime between n {\displaystyle n} and 2 n {\displaystyle 2n}, proved in 1852 by Pafnuty Chebyshev. Ideas of Bernhard Riemann in his 1859 paper on the zeta-function sketched an outline for proving the conjecture of Legendre and Gauss. Although the closely related Riemann hypothesis remains unproven, Riemann's outline was completed in 1896 by Hadamard and de la Vallée Poussin, and the result is now known as the prime number theorem. Another important 19th century result was Dirichlet's theorem on arithmetic progressions, that certain arithmetic progressions contain infinitely many primes.
  
  Many mathematicians have worked on primality tests for numbers larger than those where trial division is practicably applicable. Methods that are restricted to specific number forms include Pépin's test for Fermat numbers (1877), Proth's theorem (c. 1878), the Lucas–Lehmer primality test (originated 1856), and the generalized Lucas primality test.
  
  Since 1951 all the largest known primes have been found using these tests on computers. The search for ever larger primes has generated interest outside mathematical circles, through the Great Internet Mersenne Prime Search and other distributed computing projects. The idea that prime numbers had few applications outside of pure mathematics was shattered in the 1970s when public-key cryptography and the RSA cryptosystem were invented, using prime numbers as their basis.
  
  The increased practical importance of computerized primality testing and factorization led to the development of improved methods capable of handling large numbers of unrestricted form. The mathematical theory of prime numbers also moved forward with the Green–Tao theorem (2004) that there are arbitrarily long arithmetic progressions of prime numbers, and Yitang Zhang 's 2013 proof that there exist infinitely many prime gaps of bounded size.