Editing Prime number (section)

== History ==
[[File:Rhind Mathematical Papyrus.jpg|thumb|The [[Rhind Mathematical Papyrus]]|alt=The Rhind Mathematical Papyrus]]

The [[Rhind Mathematical Papyrus]], from around 1550 BC, has [[Egyptian fraction]] expansions of different forms for prime and composite numbers.<ref>Bruins, Evert Marie, review in ''Mathematical Reviews'' of {{cite journal | last = Gillings | first = R.J. | doi = 10.1007/BF01307175 | journal = Archive for History of Exact Sciences | mr = 0497458 | pages = 291–298 | title = The recto of the Rhind Mathematical Papyrus. How did the ancient Egyptian scribe prepare it? | volume = 12 | issue = 4 | year = 1974| s2cid = 121046003 }}</ref> However, the earliest surviving records of the study of prime numbers come from the [[Greek mathematics|ancient Greek mathematicians]], who called them {{Transliteration|grc|prōtos arithmòs}} ({{lang|grc|πρῶτος ἀριθμὸς}}). [[Euclid]]'s ''[[Euclid's Elements|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]].<ref name="stillwell-2010-p40">{{cite book|title=Mathematics and Its History|series=Undergraduate Texts in Mathematics|first=John|last=Stillwell|author-link=John Stillwell |edition=3rd |publisher=Springer |year=2010 |isbn=978-1-4419-6052-8 |page=40 |url=https://books.google.com/books?id=V7mxZqjs5yUC&pg=PA40}}</ref> Another Greek invention, the [[Sieve of Eratosthenes]], is still used to construct lists of {{nowrap|primes.<ref name="pomerance-sciam">{{cite journal |title=The Search for Prime Numbers|first=Carl|last=Pomerance|author-link=Carl Pomerance|journal=[[Scientific American]]|volume=247|issue=6|date=December 1982|pages=136–147|jstor=24966751|doi=10.1038/scientificamerican1282-136|bibcode=1982SciAm.247f.136P}}</ref><ref name="mollin">{{cite journal | last = Mollin | first = Richard A. | doi = 10.2307/3219180 | issue = 1 | journal = Mathematics Magazine | mr = 2107288 | pages = 18–29 | title = A brief history of factoring and primality testing B. C. (before computers) | volume = 75 | year = 2002| jstor = 3219180 }}</ref>}}

Around 1000&nbsp;AD, the [[Mathematics in medieval Islam|Islamic]] mathematician [[Ibn al-Haytham]] (Alhazen) found [[Wilson's theorem]], characterizing the prime numbers as the numbers {{tmath|n}} that evenly divide {{tmath|(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.<ref>{{MacTutor Biography|id=Al-Haytham|title=Abu Ali al-Hasan ibn al-Haytham|mode=cs1}}</ref> 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.<ref name="mollin"/> [[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.<ref name="mollin"/>

In 1640 [[Pierre de Fermat]] stated (without proof) [[Fermat's little theorem]] (later proved by [[Gottfried Wilhelm Leibniz|Leibniz]] and [[Leonhard Euler|Euler]]).<ref>{{harvnb|Sandifer|2007}}, [https://books.google.com/books?id=sohHs7ExOsYC&pg=PA45 8. Fermat's Little Theorem (November 2003), p. 45]</ref> Fermat also investigated the primality of the [[Fermat number]]s {{tmath|2^{2^n}+1}},<ref>{{cite book|title=How Euler Did Even More|first=C. Edward|last=Sandifer|publisher=Mathematical Association of America|year=2014|isbn=978-0-88385-584-3|page=42|url=https://books.google.com/books?id=3c6iBQAAQBAJ&pg=PA42}}</ref> and [[Marin Mersenne]] studied the [[Mersenne prime]]s, prime numbers of the form <math>2^p-1</math> with {{tmath|p}} itself a prime.<ref>{{cite book|title=Elementary Number Theory with Applications|first=Thomas|last=Koshy|publisher=Academic Press|year=2002|isbn=978-0-12-421171-1|page=369|url=https://books.google.com/books?id=-9pg-4Pa19IC&pg=PA369}}</ref> [[Christian Goldbach]] formulated [[Goldbach's conjecture]], that every even number is the sum of two primes, in a 1742 letter to Euler.<ref>{{cite book|title=Goldbach Conjecture|edition=2nd|volume=4|series=Series In Pure Mathematics|first=Wang|last=Yuan|publisher=World Scientific|year=2002|isbn=978-981-4487-52-8|page=21|url=https://books.google.com/books?id=g4jVCgAAQBAJ&pg=PA21}}</ref> Euler proved Alhazen's conjecture (now the [[Euclid–Euler theorem]]) that all even perfect numbers can be constructed from Mersenne primes.<ref name="stillwell-2010-p40"/> 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]] {{tmath|\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{5}+\tfrac{1}{7}+\tfrac{1}{11}+\cdots}}.<ref>{{cite book|title=The Development of Prime Number Theory: From Euclid to Hardy and Littlewood|series=Springer Monographs in Mathematics|first=Wladyslaw|last=Narkiewicz|publisher=Springer|year=2000|isbn=978-3-540-66289-1|page=11|contribution=1.2 Sum of Reciprocals of Primes|contribution-url=https://books.google.com/books?id=VVr3EuiHU0YC&pg=PA11}}</ref> At the start of the 19th century, Legendre and Gauss conjectured that as {{tmath|x}} tends to infinity, the number of primes up to {{tmath|x}} is [[Asymptotic analysis|asymptotic]] to {{tmath| x/\log x }}, where <math>\log x</math> is the [[natural logarithm]] of {{tmath|x}}. A weaker consequence of this high density of primes was [[Bertrand's postulate]], that for every <math>n > 1</math> there is a prime between {{tmath|n}} and {{tmath|2n}}, proved in 1852 by [[Pafnuty Chebyshev]].<ref>{{cite journal|first=P. |last=Tchebychev |author-link=Pafnuty Chebyshev |title=Mémoire sur les nombres premiers. |journal=Journal de mathématiques pures et appliquées |series=Série 1 |year=1852 |pages=366–390 |url=http://sites.mathdoc.fr/JMPA/PDF/JMPA_1852_1_17_A19_0.pdf |language=fr}}. (Proof of the postulate: 371–382). Also see Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp. 15–33, 1854</ref> Ideas of [[Bernhard Riemann]] in his [[On the Number of Primes Less Than a Given Magnitude|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 [[Jacques Hadamard|Hadamard]] and [[Charles Jean de la Vallée-Poussin|de la Vallée Poussin]], and the result is now known as the [[prime number theorem]].<ref>{{cite book | last = Apostol | first = Tom M. | author-link = Tom M. Apostol | editor1-last = Bambah | editor1-first = R.P. | editor2-last = Dumir | editor2-first = V.C. | editor3-last = Hans-Gill | editor3-first = R.J. | contribution = A centennial history of the prime number theorem | location = Basel | mr = 1764793 | pages = 1–14 | publisher = Birkhäuser | series = Trends in Mathematics | title = Number Theory | contribution-url = https://books.google.com/books?id=aiDyBwAAQBAJ&pg=PA1 | year = 2000}}</ref> Another important 19th century result was [[Dirichlet's theorem on arithmetic progressions]], that certain [[arithmetic progression]]s contain infinitely many primes.<ref>{{cite book | last = Apostol | first = Tom M. | author-link = Tom M. Apostol | contribution = 7. Dirichlet's Theorem on Primes in Arithmetical Progressions | contribution-url = https://books.google.com/books?id=3yoBCAAAQBAJ&pg=PA146 | location = New York; Heidelberg | mr = 0434929 | pages = 146–156 | publisher = Springer-Verlag | title = Introduction to Analytic Number Theory | year = 1976 }}</ref>

Many mathematicians have worked on [[primality test]]s 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),<ref>{{cite book|title=A History of Algorithms: From the Pebble to the Microchip|first=Jean-Luc|last=Chabert|publisher=Springer|year=2012|isbn=978-3-642-18192-4|page=261|url=https://books.google.com/books?id=XcDqCAAAQBAJ&pg=PA261}}</ref> [[Proth's theorem]] (c. 1878),<ref>{{cite book|title=Elementary Number Theory and Its Applications|first=Kenneth H.|last=Rosen|edition=4th|publisher=Addison-Wesley|year=2000|isbn=978-0-201-87073-2|contribution=Theorem 9.20. Proth's Primality Test|page=342}}</ref> the [[Lucas–Lehmer primality test]] (originated 1856), and the generalized [[Lucas primality test]].<ref name="mollin"/>

Since 1951 all the [[largest known prime]]s have been found using these tests on [[computer]]s.{{efn|A 44-digit prime number found in 1951 by Aimé Ferrier with a mechanical calculator remains the largest prime not to have been found with the aid of electronic computers.<ref>{{cite book|title=The Once and Future Turing|first1=S. Barry|last1=Cooper|first2=Andrew|last2=Hodges|publisher=Cambridge University Press|year=2016|isbn=978-1-107-01083-3|pages=37–38|url=https://books.google.com/books?id=h12cCwAAQBAJ&pg=PA37}}</ref>}} The search for ever larger primes has generated interest outside mathematical circles, through the [[Great Internet Mersenne Prime Search]] and other [[distributed computing]] projects.<ref name=ziegler/><ref>{{harvnb|Rosen|2000}}, p. 245.</ref> The idea that prime numbers had few applications outside of [[pure mathematics]]{{efn|name="pure"|For instance, Beiler writes that number theorist [[Ernst Kummer]] loved his [[ideal number]]s, closely related to the primes, "because they had not soiled themselves with any practical applications",<ref>{{cite book|title=Recreations in the Theory of Numbers: The Queen of Mathematics Entertains|first=Albert H.|last=Beiler|year=1999|publisher=Dover|orig-year=1966|isbn=978-0-486-21096-4|page=2|url=https://books.google.com/books?id=NbbbL9gMJ88C&pg=PA2|oclc=444171535}}</ref> and Katz writes that [[Edmund Landau]], known for his work on the distribution of primes, "loathed practical applications of mathematics", and for this reason avoided subjects such as [[geometry]] that had already shown themselves to be useful.<ref>{{cite journal | last = Katz | first = Shaul | doi = 10.1017/S0269889704000092 | issue = 1–2 | journal = Science in Context | mr = 2089305 | pages = 199–234 | title = Berlin roots&nbsp;– Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of Jerusalem | volume = 17 | year = 2004| s2cid = 145575536 }}</ref>}} was shattered in the 1970s when [[public-key cryptography]] and the [[RSA (cryptosystem)|RSA]] cryptosystem were invented, using prime numbers as their basis.<ref name="ent-7">{{cite book|title=Elementary Number Theory|series=Textbooks in mathematics|first1=James S.|last1=Kraft|first2=Lawrence C.|last2=Washington|publisher=CRC Press|year=2014|isbn=978-1-4987-0269-0|page=7|url=https://books.google.com/books?id=4NAqBgAAQBAJ&pg=PA7}}</ref>

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.<ref name="pomerance-sciam"/><ref>{{cite book|title=Secret History: The Story of Cryptology|series=Discrete Mathematics and Its Applications|first=Craig P.|last=Bauer|publisher=CRC Press|year=2013|isbn=978-1-4665-6186-1|page=468|url=https://books.google.com/books?id=EBkEGAOlCDsC&pg=PA468}}</ref><ref>{{cite book|title=Old and New Unsolved Problems in Plane Geometry and Number Theory|volume=11|series=Dolciani mathematical expositions|first1=Victor|last1=Klee|author1-link=Victor Klee|first2=Stan|last2=Wagon|author2-link=Stan Wagon|publisher=Cambridge University Press|year=1991|isbn=978-0-88385-315-3|page=224|url=https://books.google.com/books?id=tRdoIhHh3moC&pg=PA224}}</ref> 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 gap]]s of bounded size.<ref name="neale-18-47">{{harvnb|Neale|2017}}, pp. 18, 47.</ref>

=== Primality of one ===
Most early Greeks did not even consider 1 to be a number,<ref name="crxk-34">{{cite journal | last1 = Caldwell | first1 = Chris K. | last2 = Reddick | first2 = Angela | last3 = Xiong | first3 = Yeng | last4 = Keller | first4 = Wilfrid | issue = 9 | journal = [[Journal of Integer Sequences]] | mr = 3005523 | page = Article 12.9.8 | title = The history of the primality of one: a selection of sources | url = https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.html | volume = 15 | year = 2012 }} For a selection of quotes from and about the ancient Greek positions on the status of 1 and 2, see in particular pp. 3–4. For the Islamic mathematicians, see p. 6.</ref><ref>{{cite book|title=Speusippus of Athens: A Critical Study With a Collection of the Related Texts and Commentary|volume=39|series=Philosophia Antiqua : A Series of Monographs on Ancient Philosophy|first=Leonardo|last=Tarán|publisher=Brill|year=1981|isbn=978-90-04-06505-5|pages=35–38|url=https://books.google.com/books?id=cUPXqSb7V1wC&pg=PA35}}</ref> so they could not consider its primality. A few scholars in the Greek and later Roman tradition, including [[Nicomachus]], [[Iamblichus]], [[Boethius]], and [[Cassiodorus]], also considered the prime numbers to be a subdivision of the odd numbers, so they did not consider {{tmath|2}} to be prime either. However, Euclid and a majority of the other Greek mathematicians considered {{tmath|2}} as prime. The [[Mathematics in medieval Islam|medieval Islamic mathematicians]] largely followed the Greeks in viewing 1 as not being a number.<ref name="crxk-34"/> By the Middle Ages and Renaissance, mathematicians began treating 1 as a number, and by the 17th century some of them included it as the first prime number.<ref>{{harvnb|Caldwell|Reddick|Xiong|Keller|2012}}, pp. 7–13. See in particular the entries for Stevin, Brancker, Wallis, and Prestet.</ref> In the mid-18th century, [[Christian Goldbach]] listed 1 as prime in his correspondence with [[Leonhard Euler]];<ref>{{harvnb|Caldwell|Reddick|Xiong|Keller|2012}}, pp. 6–7.</ref> however, Euler himself did not consider 1 to be prime.<ref>{{harvnb|Caldwell|Reddick|Xiong|Keller|2012}}, p. 15.</ref> Many 19th century mathematicians still considered 1 to be prime,<ref name="cx"/> and [[Derrick Norman Lehmer]] included 1 in his ''list of primes less than ten million'' published in 1914.{{sfn|Conway|Guy|1996|pp=130}} Lists of primes that included 1 continued to be published as recently {{nowrap|as 1956.<ref>{{cite book | last=Riesel | first=Hans | author-link= Hans Riesel | title=Prime Numbers and Computer Methods for Factorization | publisher=Birkhäuser | location=Basel, Switzerland | isbn=978-0-8176-3743-9 | year=1994|page=36|edition=2nd|mr=1292250|url=https://books.google.com/books?id=ITvaBwAAQBAJ&pg=PA36 | doi=10.1007/978-1-4612-0251-6 }}</ref><ref name="cg-bon-129-130">{{cite book | last1=Conway | first1=John Horton | author1-link=John Horton Conway | last2=Guy | first2=Richard K. | author2-link=Richard K. Guy | title=The Book of Numbers |title-link=The Book of Numbers (math book) | publisher=Copernicus | location=New York | isbn=978-0-387-97993-9 | year=1996 | pages = [https://archive.org/details/bookofnumbers0000conw/page/129 129–130] | mr=1411676 | doi=10.1007/978-1-4612-4072-3 }}</ref>}} However, by the early 20th century mathematicians began to agree that 1 should not be listed as prime, but rather in its own special category as a "[[Unit (ring theory)|unit]]".<ref name="cx"/><!--pp=6-8-->

If 1 were to be considered a prime, many statements involving primes would need to be awkwardly reworded. For example, the fundamental theorem of arithmetic would need to be rephrased in terms of factorizations into primes greater than 1, because every number would have multiple factorizations with any number of copies of&nbsp;1.<ref name="cx">{{cite journal | last1 = Caldwell | first1 = Chris K. | last2 = Xiong | first2 = Yeng | issue = 9 | journal = [[Journal of Integer Sequences]] | mr = 3005530 | page = Article 12.9.7 | title = What is the smallest prime? | url = https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.pdf | volume = 15 | year = 2012}}</ref> Similarly, the [[sieve of Eratosthenes]] would not work correctly if it handled 1 as a prime, because it would eliminate all multiples of 1 (that is, all other numbers) and output only the single number&nbsp;1.<ref name="cg-bon-129-130"/> Some other more technical properties of prime numbers also do not hold for the number 1: for instance, the formulas for [[Euler's totient function]] or for the [[Sum-of-divisors function|sum of divisors function]] are different for prime numbers than they are for&nbsp;1.<ref>For the totient, see {{harvnb|Sierpiński|1988}}, [https://books.google.com/books?id=ktCZ2MvgN3MC&pg=PA245 p. 245]. For the sum of divisors, see {{cite book|title=How Euler Did It|series=MAA Spectrum|first=C. Edward|last=Sandifer|publisher=Mathematical Association of America|year=2007|isbn=978-0-88385-563-8|page=59|url=https://books.google.com/books?id=sohHs7ExOsYC&pg=PA59}}</ref>