Skip to content
— CH. 1 · INTRODUCTION —

Prime number

10 min listen · Ch. 1 of 8
8 sections
  • The number 5 cannot be broken apart. Write it as a product and the only options are 1 times 5 or 5 times 1, each of which still leans on the 5 itself. The number 4 has no such defense. It folds neatly into 2 times 2, two smaller numbers locked together. This is the dividing line that defines a prime number, a natural number greater than 1 that is not the product of two smaller natural numbers. A number greater than 1 that is not prime is called composite. From this plain rule grows one of the oldest and deepest subjects in mathematics. Why did the ancient Greeks call these numbers protos arithmos, and why did Euclid prove around 300 BC that they never run out? Why does a question as simple as Goldbach's conjecture stay unsolved for centuries, even after being verified for staggering ranges of numbers? And how did a field that mathematicians once prized for having no use at all become the hidden machinery behind public-key cryptography? The answers run from a papyrus dated to around 1550 BC to a Mersenne prime with more than 41 million digits found in October 2024.

  • Every integer larger than 1 can be written as a product of one or more primes, and that is why mathematicians call primes the basic building blocks of the natural numbers. This statement is the fundamental theorem of arithmetic. It says more than that a factorization exists. It says the factorization is unique. Any two prime factorizations of the same number contain the same primes in the same quantities, differing only in the order you write them. A single prime factor can appear more than once, and exponentiation groups those repeated copies together. Many proofs of this uniqueness rest on Euclid's lemma. If a prime divides a product of two integers, then it must divide at least one of those two integers. The reverse holds as well. If a number always divides at least one factor whenever it divides a product, that number must itself be prime. This building-block idea also explains a small set of useful shortcuts about which numbers can be prime. No even number above 2 is prime, since any such number splits off a factor of 2, so every prime past 2 is odd. In the decimal system, every prime larger than 5 ends in 1, 3, 7, or 9, because numbers ending in 0, 2, 4, 6, or 8 are even and numbers ending in 0 or 5 are divisible by 5. The first twenty-five primes, all those below 100, begin 2, 3, 5, 7, 11 and end at 89 and 97.

  • Most early Greeks did not even regard 1 as a number, so they never asked whether it was prime. Scholars including Nicomachus, Iamblichus, Boethius, and Cassiodorus treated primes as a subset of the odd numbers, which left 1 outside the question entirely. Euclid and most other Greek mathematicians, by contrast, did count 1 as prime. Attitudes drifted over centuries. Medieval Islamic mathematicians mostly followed the Greeks in denying that 1 was a number at all. By the Middle Ages and Renaissance, mathematicians began treating 1 as a number, and by the 17th century some listed it as the first prime. Christian Goldbach put 1 among the primes in his letters to Leonhard Euler, though Euler did not agree. The habit lingered for a long time. Derrick Norman Lehmer included 1 in his list of primes below ten million, published in 1914, and lists with 1 as a prime were still appearing as late as 1956. The reason 1 was eventually exiled into its own category as a unit is practical. If 1 counted as prime, the fundamental theorem of arithmetic would break, because any number could absorb extra copies of 1 and gain endless factorizations. The sieve of Eratosthenes would collapse too, striking out every multiple of 1 and leaving only the number 1 behind.

  • Euclid's theorem holds that the primes never end, and the first known proof of it is credited to him. The argument is a trap built from any finite list of primes you care to name. Multiply all of them together and add one. By the fundamental theorem of arithmetic, this new number has its own prime factorization. Yet it leaves a remainder of one when divided by any prime on your original list, so none of its prime factors can be among them. Every finite list is therefore incomplete, which means the supply must be infinite. The numbers formed by adding one to the products of the smallest primes carry the name Euclid numbers. The first five of them are prime, but the sixth turns out to be composite. Euclid's was only the first of many proofs. Euler supplied an analytical one, Goldbach built a proof from Fermat numbers, Furstenberg constructed one out of general topology, and Kummer argued by contradiction. The endlessness of the primes raised a harder question once it was settled. If they never stop, how are they spread out, and is there any pattern to where the next one falls?

  • No known simple formula separates the primes from the composites, and there is no non-constant polynomial, even in several variables, that produces only prime values. There are stranger constructions that do encode the primes. One formula built on Wilson's theorem generates the number 2 repeatedly and every other prime exactly once. A system of Diophantine equations in nine variables has a parameter that is prime precisely when the system has a solution in natural numbers, which yields a single formula whose positive values are all prime. Mills' theorem and a theorem of Wright provide real constants that generate primes through the floor function, but these are useless in practice, because you must already know the primes to compute the constants. Where exact formulas fail, statistics succeeds. The prime number theorem, proven at the close of the 19th century, says roughly that a large number's chance of being prime is inversely proportional to its number of digits, that is, to its logarithm. The road to that theorem was long. Legendre and Gauss conjectured the asymptotic count of primes at the start of the 19th century. Pafnuty Chebyshev proved Bertrand's postulate in 1852, guaranteeing a prime in certain intervals. Bernhard Riemann's 1859 paper on the zeta-function sketched the outline that Hadamard and de la Vallee Poussin completed in 1896.

  • All four of Landau's problems from 1912 remain unsolved, a reminder that simple-sounding questions about primes can resist proof for over a century. Goldbach's conjecture is among them. It claims that every even integer greater than 2 is the sum of two primes, and it has been verified for enormous ranges of numbers without ever failing or being proven. Weaker results have fallen. Vinogradov's theorem shows that every sufficiently large odd integer is a sum of three primes, and Chen's theorem shows every sufficiently large even number is a prime plus a semiprime. The twin prime conjecture asks whether infinitely many pairs of primes differ by 2, and Polignac's conjecture extends the idea to every fixed even gap. Prime gaps, the distances between consecutive primes, hold their own surprises. Arbitrarily large gaps must exist, yet they arrive far sooner than the simplest argument predicts. The first prime gap of length 8 sits between 89 and 97. Progress on these questions has been real. The Green-Tao theorem of 2004 showed there are arbitrarily long arithmetic progressions made entirely of primes. Yitang Zhang proved in 2013 that infinitely many prime gaps are bounded in size.

  • British mathematician G. H. Hardy prided himself on doing work with absolutely no military significance, and for a long time the study of primes was the textbook case of pure mathematics. The only application anyone could point to was using a prime number of gear teeth to spread wear evenly. That self-image broke apart in the 1970s, when it became public that primes could anchor public-key cryptography and the RSA cryptosystem. RSA leans on a stark imbalance. Multiplying two large primes is easy, but recovering those primes from the product alone is hard, and that asymmetry guards the system. The Diffie-Hellman key exchange relies on a similar gap, between fast modular exponentiation and the difficult reverse problem of the discrete logarithm. Today 2048-bit primes are common in such systems. The work of generating large random primes drove the study of primality testing. Trial division divides a candidate by each integer up to its square root, declaring it composite at the first clean division and prime otherwise. To test 37, you divide only by the primes 2, 3, and 5, each leaving a remainder, so 37 is prime. That method is too slow for large numbers, where the number of tests grows exponentially with the digit count, so it now serves mainly to strip out small factors before heavier methods take over.

  • Olivier Messiaen used the primes 41, 43, 47, and 53 in the third etude of his Quatre etudes de rythme, titled Neumes rythmiques, layering motifs of those lengths to build rhythms that never quite repeat. The French composer called this approach inspired by the movements of nature, movements of free and unequal durations, and he reached for it again in works such as La Nativite du Seigneur from 1935. Primes have drawn writers as much as composers. In his novel Contact, Carl Sagan proposed prime factorization as a way to build image planes in messages to aliens, an idea he had first sketched informally with American astronomer Frank Drake in 1975. Mark Haddon ordered the chapters of The Curious Incident of the Dog in the Night-Time by consecutive primes to mirror the mind of his narrator. Paolo Giordano cast them as outsiders in The Solitude of Prime Numbers, a metaphor for loneliness. Nature uses them too. Cicadas of the genus Magicicada emerge from underground only after 7, 13, or 17 years, prime-numbered cycles that biologists believe evolved to keep predators from synchronizing with them. The same logic of indecomposability reappears in knot theory, where any knot breaks uniquely into prime knots, just as the energy levels of quantum systems have been speculatively linked to the zeros of the Riemann zeta function ever since the 1970s work of Hugh Montgomery and Freeman Dyson.

Common questions

What is a prime number?

A prime number is a natural number greater than 1 that is not the product of two smaller natural numbers. For example, 5 is prime because the only ways to write it as a product, 1 times 5 or 5 times 1, involve 5 itself, while 4 is composite because it equals 2 times 2.

Why is the number 1 not considered a prime number?

The number 1 is excluded from the primes and placed in its own category as a unit because counting it as prime would break key results. The fundamental theorem of arithmetic would fail, since every number could gain endless factorizations using copies of 1, and the sieve of Eratosthenes would eliminate all multiples of 1 and output only 1.

How do you prove there are infinitely many prime numbers?

Euclid proved around 300 BC that the primes are infinite by showing every finite list of them is incomplete. Multiplying the listed primes together and adding one gives a number that leaves a remainder of one when divided by any prime on the list, so its prime factors must lie outside the list.

What is Goldbach's conjecture about prime numbers?

Goldbach's conjecture asserts that every even integer greater than 2 can be written as the sum of two primes. Christian Goldbach formulated it in a 1742 letter to Leonhard Euler, and it has been verified for large ranges of numbers but remains unproven.

How are prime numbers used in cryptography?

Prime numbers are the basis of public-key cryptography, including the RSA cryptosystem and the Diffie-Hellman key exchange, with 2048-bit primes common. RSA relies on the difficulty of factoring large numbers into their prime factors, since multiplying two large primes is easy but recovering them from the product is hard.

What is the largest known prime number?

The largest known prime is the Mersenne prime 2 to the power 136,279,841 minus 1, which has 41,024,320 decimal digits. It was found on the 12th of October 2024 by Luke Durant and the Great Internet Mersenne Prime Search, and since 1992 the largest known prime has always been a Mersenne prime.

All sources

163 references cited across the entry

  1. 2BookDyslexia, Dyscalculia and Mathematics: A practical guideAnne Henderson — Routledge — 2014
  2. 4BookMath Workbook for the SAT ILawrence S. Leff — Barron's Educational Series — 2000
  3. 5BookElementary number theoryUnderwood Dudley — W.H. Freeman and Co. — 1978
  4. 6BookElementary Theory of NumbersWacław Sierpiński — Elsevier — 1988
  5. 7JournalThe great prime number record racesGünter M. Ziegler — 2004
  6. 8BookNumbers and GeometryJohn Stillwell — Springer — 1997
  7. 9BookA Selection of Problems in the Theory of NumbersWacław Sierpiński — Macmillan — 1964
  8. 10BookElementary Methods in Number TheoryMelvyn B. Nathanson — Springer — 2000
  9. 11BookThe Mathematics of Infinity: A Guide to Great IdeasTheodore G. Faticoni — John Wiley & Sons — 2012
  10. 12JournalTechniques of fractions in ancient Egypt and GreeceWilbur Knorr — 1982
  11. 13BookMathematics and Its HistoryJohn Stillwell — Springer — 2010
  12. 14JournalThe Search for Prime NumbersCarl Pomerance — December 1982
  13. 15JournalA brief history of factoring and primality testing B. C. (before computers)Richard A. Mollin — 2002
  14. 16Sandifer (2007)Sandifer — 2007
  15. 17BookHow Euler Did Even MoreC. Edward Sandifer — Mathematical Association of America — 2014
  16. 18BookElementary Number Theory with ApplicationsThomas Koshy — Academic Press — 2002
  17. 19BookGoldbach ConjectureWang Yuan — World Scientific — 2002
  18. 20BookThe Development of Prime Number Theory: From Euclid to Hardy and LittlewoodWladyslaw Narkiewicz — Springer — 2000
  19. 21JournalMémoire sur les nombres premiers.P. Tchebychev — 1852
  20. 22BookNumber TheoryTom M. Apostol — Birkhäuser — 2000
  21. 23BookIntroduction to Analytic Number TheoryTom M. Apostol — Springer-Verlag — 1976
  22. 24BookA History of Algorithms: From the Pebble to the MicrochipJean-Luc Chabert — Springer — 2012
  23. 25BookElementary Number Theory and Its ApplicationsKenneth H. Rosen — Addison-Wesley — 2000
  24. 26BookThe Once and Future TuringS. Barry Cooper et al. — Cambridge University Press — 2016
  25. 27Rosen (2000)Rosen — 2000
  26. 29JournalBerlin roots – Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of JerusalemShaul Katz — 2004
  27. 30BookElementary Number TheoryJames S. Kraft et al. — CRC Press — 2014
  28. 31BookSecret History: The Story of CryptologyCraig P. Bauer — CRC Press — 2013
  29. 32BookOld and New Unsolved Problems in Plane Geometry and Number TheoryVictor Klee et al. — Cambridge University Press — 1991
  30. 33Neale (2017)Neale — 2017
  31. 34JournalThe history of the primality of one: a selection of sourcesChris K. Caldwell et al. — 2012
  32. 36Caldwell, Reddick, Xiong (2012)Caldwell, Reddick, Xiong — 2012
  33. 37BookPrime Numbers and Computer Methods for FactorizationHans Riesel — Birkhäuser — 1994
  34. 38BookThe Book of NumbersJohn Horton Conway et al. — Copernicus — 1996
  35. 39JournalWhat is the smallest prime?Chris K. Caldwell et al. — 2012
  36. 40BookIs Math Real? How Simple Questions Lead Us to Mathematics' Deepest TruthsEugenia Cheng — Basic Books — 2023
  37. 41Sierpiński (1988)Sierpiński — 1988
  38. 42BookThe Nature of MathematicsKarl J. Smith — Cengage Learning — 2011
  39. 43Dudley (1978)Dudley — 1978
  40. 45BookA First Course in Abstract AlgebraJoseph J. Rotman — Prentice Hall — 2000
  41. 47JournalOn the infinitude of primesHarry Furstenberg — 1955
  42. 48BookThe little book of bigger primesPaulo Ribenboim — Springer-Verlag — 2004
  43. 50BookThe Elements of Euclid, With DissertationsJames Williamson — Clarendon Press — 1782
  44. 51BookComputational Recreations in MathematicaIlan Vardi — Addison-Wesley — 1991
  45. 52JournalPrime number formulaeNick Mackinnon — June 1987
  46. 53BookKvant Selecta: Algebra and AnalysisYuri V. Matiyasevich — American Mathematical Society — 1999
  47. 54JournalA prime-representing functionE.M. Wright — 1951
  48. 55Guy (2013)Guy — 2013
  49. 56JournalEmpirical verification of the even Goldbach conjecture and computation of prime gaps up toTomás Oliveira e Silva et al. — 2014
  50. 57Tao (2009)Tao — 2009
  51. 58JournalOn Šnirel'man's constantOlivier Ramaré — 1995
  52. 59BookGoldbach's Problem: Selected TopicsMichael Th. Rassias — Springer — 2017
  53. 60Koshy (2002)Koshy — 2002
  54. 61Ribenboim (2004)Ribenboim — 2004
  55. 62JournalPrime time!Joel Chan — February 1996
  56. 63BookExcursions in Number TheoryC.S. Ogilvy et al. — Dover Publications Inc. — 1988
  57. 64Apostol (1976)Apostol — 1976
  58. 65BookAn Invitation to Modern Number TheorySteven J. Miller et al. — Princeton University Press — 2006
  59. 66Crandall, Pomerance (2005)Crandall, Pomerance — 2005
  60. 67BookThe Number Mysteries: A Mathematical Odyssey through Everyday LifeMarcus du Sautoy — St. Martin's Press — 2011
  61. 68Riesel (1994)Riesel — 1994
  62. 69BookAlgebraIsrael M. Gelfand et al. — Springer — 2003
  63. 70BookFundamental Number Theory with ApplicationsRichard A. Mollin — CRC Press — 1997
  64. 71JournalThe primes contain arbitrarily long arithmetic progressionsBen Green et al. — 2008
  65. 72BookAdditive Theory of Prime NumbersL. K. Hua — American Mathematical Society — 2009
  66. 73Book103 curiosità matematiche: Teoria dei numeri, delle cifre e delle relazioni nella matematica contemporaneaPaolo Pietro Lava et al. — Ulrico Hoepli Editore S.p.A. — 2010
  67. 74BookSingle Digits: In Praise of Small NumbersMarc Chamberland — Princeton University Press — 2015
  68. 75BookUnsolved Problems in Number TheoryRichard Guy — Springer — 2013
  69. 76JournalA Visual Display of Some Properties of the Distribution of PrimesM.L. Stein et al. — 1964
  70. 77The Riemann Hypothesis – official problem descriptionEnrico Bombieri — Clay Mathematics Institute — 2000
  71. 78BookAn introduction to the theory of the Riemann zeta-functionS. J. Patterson — Cambridge University Press, Cambridge — 1988
  72. 80Borwein, Choi, Rooney (2008)Borwein, Choi, Rooney — 2008
  73. 81Patterson (1988)Patterson — 1988
  74. 82Nathanson (2000)Nathanson — 2000
  75. 83JournalThe first 50 million prime numbersDon Zagier — 1977
  76. 85BookAlgebra in Action: A Course in Groups, Rings, and FieldsShahriar Shahriari — American Mathematical Society — 2017
  77. 86Shahriari (2017)Shahriari — 2017
  78. 87BookIntroduction to Number TheoryMarty Erickson et al. — CRC Press — 2016
  79. 88BookClass Field TheoryNancy Childress — Springer, New York — 2009
  80. 89BookBasic Number TheoryAndré Weil — Springer-Verlag — 1995
  81. 90BookAlgebraic Number TheoryH. Koch — Springer-Verlag — 1997
  82. 91BookConcrete Abstract Algebra: From numbers to Gröbner basesNiels Lauritzen — Cambridge University Press — 2003
  83. 92Lauritzen (2003)Lauritzen — 2003
  84. 93Kraft, Washington (2014)Kraft, Washington — 2014
  85. 94BookCommutative AlgebraDavid Eisenbud — Springer-Verlag — 1995
  86. 95BookBasic Algebraic Geometry 2: Schemes and Complex ManifoldsIgor R. Shafarevich — Springer, Heidelberg — 2013
  87. 96BookAlgebraic Number TheoryJürgen Neukirch — Springer-Verlag — 1999
  88. 97Neukirch (1999)Neukirch — 1999
  89. 98JournalChebotarëv and his density theoremP. Stevenhagen et al. — 1996
  90. 99BookThe Theory of GroupsMarshall Hall — Courier Dover Publications — 2018
  91. 100BookHow Round is Your Circle?: Where Engineering and Mathematics MeetJohn Bryant et al. — Princeton University Press — 2008
  92. 101BookA Mathematician's ApologyGodfrey Harold Hardy — Cambridge University Press — 2012
  93. 102BookPrimes and ProgrammingPeter Giblin — Cambridge University Press — 1993
  94. 103Giblin (1993)Giblin — 1993
  95. 105BookThe Joy of FactoringSamuel S. Jr. Wagstaff — American Mathematical Society — 2013
  96. 106BookPrime Numbers: A Computational PerspectiveRichard Crandall et al. — Springer — 2005
  97. 107Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, ProceedingsMartín Farach-Colton et al. — Springer — 2015
  98. 108BookSieves in Number TheoryGeorge Greaves — Springer — 2013
  99. 109BookAlgorithmics for Hard ProblemsJuraj Hromkovič — Springer-Verlag, Berlin — 2001
  100. 110BookFundamentals of Computer SecurityJosef Pieprzyk et al. — Springer — 2013
  101. 111BookA Course in Number Theory and CryptographyNeal Koblitz — Springer-Verlag, New York — 1987
  102. 112BookAn epsilon of room, II: Pages from year three of a mathematical blogTerence Tao — American Mathematical Society — 2010
  103. 113JournalElliptic curves and primality provingA O.L. Atkin et al. — 1993
  104. 114JournalPrimality testing with Gaussian periodsH. W. Jr. Lenstra et al. — 2019
  105. 115JournalImplementing the asymptotically fast version of the elliptic curve primality proving algorithmF. Morain — 2007
  106. 116JournalThe pseudoprimes to 25·109Carl Pomerance et al. — July 1980
  107. 117JournalLucas PseudoprimesRobert Baillie et al. — October 1980
  108. 118JournalEvaluation and comparison of two efficient probabilistic primality testing algorithmsLouis Monier — 1980
  109. 119BookPoincaré's legacies, pages from year two of a mathematical blog. Part ITerence Tao — American Mathematical Society — 2009
  110. 120Record 12-Million-Digit Prime Number Nets $100,000 PrizeElectronic Frontier Foundation — October 14, 2009
  111. 121EFF Cooperative Computing AwardsElectronic Frontier Foundation — 2008-02-29
  112. 125The Top Twenty: FactorialChris K. Caldwell
  113. 126The Top Twenty: PrimorialChris K. Caldwell
  114. 127The Top Twenty: Twin PrimesChris K. Caldwell
  115. 128BookAn Introduction to Mathematical CryptographyJeffrey Hoffstein et al. — Springer — 2014
  116. 129JournalA tale of two sievesCarl Pomerance — 1996
  117. 130795-bit factoring and discrete logarithmsEmmanuel Thomé — December 2, 2019
  118. 131BookQuantum Computing: A Gentle IntroductionEleanor G. Rieffel et al. — MIT Press — 2011
  119. 132JournalExperimental realization of Shor's quantum factoring algorithm using qubit recyclingEnrique Martín-López et al. — 12 October 2012
  120. 133NewsCrypto needs more transparency, researchers warnRichard Chirgwin — October 9, 2016
  121. 134Hoffstein, Pipher, Silverman (2014)Hoffstein, Pipher, Silverman — 2014
  122. 135BookData Structures & Algorithms in JavaMichael T. Goodrich et al. — John Wiley & Sons — 2006
  123. 136BookIdentification Numbers and Check Digit SchemesJoseph Kirtland — Mathematical Association of America — 2001
  124. 137ZLIB Compressed Data Format Specification version 3.3P. Deutsch — Network Working Group — May 1996
  125. 138BookThe Art of Computer Programming, Vol. 2: Seminumerical algorithmsDonald E. Knuth — Addison-Wesley — 1998
  126. 139JournalMersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generatorMakoto Matsumoto et al. — 1998
  127. 140JournalOn a problem of HeilbronnKlaus F. Roth — 1951
  128. 142BookAlgebraSerge Lang — Springer-Verlag — 2002
  129. 143JournalDie eindeutige Zerlegbarkeit eines Knotens in PrimknotenHorst Schubert — 1949
  130. 144JournalA unique decomposition theorem for 3-manifoldsJ. Milnor — 1962
  131. 145Book17 Lectures on Fermat Numbers: From Number Theory to GeometryMichal Křížek et al. — Springer-Verlag — 2001
  132. 146JournalExpect at most one billionth of a new Fermat prime!Kent D. Boklan et al. — January 2017
  133. 147JournalAngle trisection, the heptagon, and the triskaidecagonAndrew M. Gleason — 1988
  134. 148JournalCannons at sparrowsGünter M. Ziegler — 2015
  135. 149The Return of ZetaIvars Peterson — June 28, 1999
  136. 150JournalComputing science: The spectrum of RiemanniumBrian Hayes — 2003
  137. 151BookGeometry of quantum states: an introduction to quantum entanglementIngemar Bengtsson et al. — Cambridge University Press — 2017
  138. 153JournalPrime number selection of cycles in a predator-prey modelE. Goles et al. — 2001
  139. 154JournalEmergence of prime numbers as the result of evolutionary strategyPaulo R. A. Campos et al. — 2004
  140. 155NewsInvasion of the BroodMay 6, 2004
  141. 156MagazineBamboo MathematiciansCarl Zimmer — May 15, 2015
  142. 157BookThe Messiaen companionAmadeus Press — 1995
  143. 158BookMathematical Adventures for Students and AmateursCarl Pomerance — Mathematical Association of America — 2004
  144. 159NewsThe Curious Incident of the Dog in the Night-TimeGrrlScientist — September 16, 2010
  145. 160NewsCounting on Each OtherLiesl Schillinger — April 9, 2010
  146. 161SneakersLen Adleman — University of Southern California
  147. 162JournalMathematicians in the MoviesConstance Reid — 1994