# Prime number
A **prime number**, or simply a prime in everyday usage, is any natural number greater than 1 that admits no factorization as a product of two smaller natural numbers; 2, 3, 5, and 7 are examples[1](https://www.claymath.org/library/public_lectures/mazur_riemann_hypothesis.pdf). Primes are the multiplicative building blocks of the integers: the [fundamental theorem of arithmetic](https://www.edgepedia.org/fundamental-theorem-of-arithmetic) states that any positive integer can be represented in exactly one way as a product of primes[2](https://mathworld.wolfram.com/PrimeNumber.html). They play an important role in pure mathematics and in applications, most visibly in public key cryptography[1](https://www.claymath.org/library/public_lectures/mazur_riemann_hypothesis.pdf).
| Key fact | Detail |
|---|---|
| Definition | A whole number greater than 1 with no factorization into two smaller whole numbers; 1 is neither prime nor composite[1](https://www.claymath.org/library/public_lectures/mazur_riemann_hypothesis.pdf) • [2](https://mathworld.wolfram.com/PrimeNumber.html) |
| Smallest prime | 2, the only even prime[2](https://mathworld.wolfram.com/PrimeNumber.html) |
| Infinitude | Euclid proved in Book IX of the *Elements* (about 300 BC) that there are infinitely many primes[3](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/) |
| Distribution | The number of primes below x is asymptotic to x/log(x), proved in 1896 by Hadamard and de la Vallée Poussin[4](https://www.claymath.org/collections/riemanns-1859-manuscript/) |
| Largest known prime | 2136,279,841 − 1, with 41,024,320 decimal digits, found October 12, 2024 by GIMPS[5](https://www.mersenne.org/primes/?press=M136279841) |
| Cryptographic use | RSA-style public key codes multiply two secret primes of about 400 decimal digits each into a public 800-digit product[6](https://dlmf.nist.gov/27.16) |
| Open problem | The twin prime conjecture (infinitely many prime pairs differing by 2) remains unproved; bounded gaps of at most 246 are proved[7](https://mathworld.wolfram.com/TwinPrimeConjecture.html) |
## Definition and basic properties
By definition, a prime is a whole number bigger than 1 that cannot be written as a product of two smaller whole numbers[1](https://www.claymath.org/library/public_lectures/mazur_riemann_hypothesis.pdf). An integer greater than 1 that does factor this way, such as 4, 6, 8, or 9, is called composite[8](https://www.southampton.ac.uk/~wright/1001/chapter-primes.html).
**The status of 1.** The number 1 is a special case considered neither prime nor composite[2](https://mathworld.wolfram.com/PrimeNumber.html). Excluding it keeps the fundamental theorem of arithmetic true as stated, since if 1 were prime, factorization "in exactly one way" would fail because any n = n · 1[2](https://mathworld.wolfram.com/PrimeNumber.html). Historically the question is a matter of definition: for the ancient Greeks, numbers (αριθμος) were multiples of the unit, so one did not fall into the category of primes at all, and a historical survey by Angela Reddick and Yeng Xiong found that for most of history one was not considered a prime, with no point in time where a clear majority of mathematicians viewed it as prime[9](https://scholarexchange.furman.edu/fuejum/vol16/iss1/1/).
With 1 excluded, the smallest prime is 2, which is also the only even prime; the set of all primes excluding 2 is called the odd primes[2](https://mathworld.wolfram.com/PrimeNumber.html).
## Early history
Prime numbers and their properties were first studied extensively by the ancient Greek mathematicians[3](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/). By the time Euclid's *Elements* appeared in about 300 BC, several important results had been proved: Book IX contains the proof that there are infinitely many primes, one of the first known proofs by contradiction, and Euclid also gave a proof of the fundamental theorem of arithmetic[3](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/). The proof supposes the only primes are p₁, p₂, ..., p_k and considers m = p₁p₂...p_k + 1; since m is greater than 1 it has a prime divisor, which cannot be any of the listed primes without dividing 1, a contradiction[8](https://www.southampton.ac.uk/~wright/1001/chapter-primes.html).
In about 200 BC Eratosthenes devised the [Sieve of Eratosthenes](https://www.edgepedia.org/sieve-of-eratosthenes), an algorithm that finds all primes up to a limit by striking out multiples of each prime in turn, leaving only primes[3](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/). After the Greeks, the history shows a long gap during the Dark Ages, with the next important developments made by Fermat at the beginning of the 17th century[3](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/).
**Fermat's little theorem.** Fermat proved that if p is prime, then for any integer a we have ap = a modulo p[3](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/). This theorem is the basis for methods of checking whether numbers are prime that are still in use on today's electronic computers[3](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/). The converse fails: 2341 − 2 is divisible by 341 even though 341 = 31 × 11 is composite, so such tests are probabilistic in character[3](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/).
## Distribution of primes
The distribution of primes among the natural numbers does not follow any regular pattern[10](https://www.claymath.org/millennium/riemann-hypothesis/). Yet there is a precise average law. First proposed by Gauss in his youth, the prime number theorem says that the count of primes below x is asymptotic to x/log(x); in rough terms, if a number near x is picked at random, its chance of being prime is about 1/log(x)[4](https://www.claymath.org/collections/riemanns-1859-manuscript/). Riemann's 1859 paper, just six manuscript pages long, introduced ideas that led in 1896 to independent proofs of the theorem by Hadamard and de la Vallée Poussin[4](https://www.claymath.org/collections/riemanns-1859-manuscript/).
**The Riemann hypothesis.** Riemann observed that the frequency of primes is closely related to the behavior of the [Riemann zeta function](https://www.edgepedia.org/riemann-zeta-function) ζ(s) = 1 + 1/2s + 1/3s + 1/4s + ...[10](https://www.claymath.org/millennium/riemann-hypothesis/). His hypothesis asserts that all the non-obvious zeros of ζ(s) are complex numbers with real part 1/2; it has been checked for the first 10,000,000,000,000 solutions, but a proof remains outstanding[10](https://www.claymath.org/millennium/riemann-hypothesis/). The prime number theorem describes the average distribution of the primes, and the [Riemann hypothesis](https://www.edgepedia.org/riemann-hypothesis) describes the deviation from that average[10](https://www.claymath.org/millennium/riemann-hypothesis/). It is one of the seven Clay Millennium Prize Problems[4](https://www.claymath.org/collections/riemanns-1859-manuscript/).
## Gaps and conjectures
The prime number theorem shows that the gap between consecutive primes is on average about log n[11](https://www.ams.org/journals/notices/202004/202004FullIssue.pdf). Whether small gaps recur infinitely often is a famous open question: the twin prime conjecture states that there are infinitely many pairs of primes differing by 2[7](https://mathworld.wolfram.com/TwinPrimeConjecture.html).
**Bounded gaps.** In 2013 [Yitang Zhang](https://www.edgepedia.org/yitang-zhang) announced a proof of the bounded gaps conjecture, establishing a natural number H such that infinitely many pairs of distinct primes p, q satisfy |p − q| < H[12](https://blogs.ams.org/mathgradblog/2013/06/24/small-gap-be-a-huge-landmark-number-theory/). Zhang's original bound was below 70 million[12](https://blogs.ams.org/mathgradblog/2013/06/24/small-gap-be-a-huge-landmark-number-theory/). James Maynard, using multidimensional sieve weights developed independently by [Terence Tao](https://www.edgepedia.org/terence-tao), re-proved the result in simpler and stronger form and showed that for each k, infinitely many n have k primes in an interval of bounded length[13](https://www.ams.org/notices/201506/rnoti-p660.pdf). The Polymath project established the unconditional bound H₁ ≤ 246, giving infinitely many pairs of consecutive primes separated by at most 246; this does not show that gap 2 occurs infinitely often, so the twin prime conjecture remains open[7](https://mathworld.wolfram.com/TwinPrimeConjecture.html).
A related proved result is Brun's theorem: the sum of the reciprocals of the twin primes converges to a definite number, expressing the scarcity of twin primes even if there are infinitely many, while the series of all prime reciprocals diverges to infinity[14](https://mathworld.wolfram.com/TwinPrimes.html).
## Largest known primes and computation
Numbers of the form 2n − 1, called Mersenne numbers, have long provided the largest known primes[3](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/). In 1952 the Mersenne numbers M₅₂₁, M₆₀₇, M₁₂₇₉, M₂₂₀₃, and M₂₂₈₁ were proved prime by Robinson using an early computer, beginning the electronic era[3](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/). By 2018 a total of 50 [Mersenne primes](https://www.edgepedia.org/mersenne-primes) had been found[3](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/).
The current record is 2136,279,841 − 1, having 41,024,320 decimal digits, discovered on October 12, 2024 by Luke Durant of San Jose, California, through the [Great Internet Mersenne Prime Search](https://www.edgepedia.org/great-internet-mersenne-prime-search) (GIMPS)[5](https://www.mersenne.org/primes/?press=M136279841). It is the 52nd known [Mersenne prime](https://www.edgepedia.org/mersenne-prime), over 16 million digits larger than the previous record, and was found using PRP testing with Gpuowl on an [NVIDIA A100](https://www.edgepedia.org/nvidia-a100)[5](https://www.mersenne.org/primes/?press=M136279841) • [15](https://www.mersenne.org/primes/).
Finding primes is far easier than factoring. Near a number of size x, roughly ln x numbers must be tested before a prime is found, and ignoring evens reduces this to about (ln x)/2; for a 100-digit prime that is about 115 odd candidates, and eliminating multiples of small primes reduces the count further[16](https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-2.pdf).
## Applications in cryptography
Cryptographic applications depend on the fact that computers need far less time to locate large primes than to factor large integers.[6](https://dlmf.nist.gov/27.16) In a typical public key construction, a code maker chooses two large primes p and q of about 400 decimal digits each, a task requiring very little computer time; the primes are kept secret while their product n = pq, an 800-digit number, is made public. Messages are coded using only n, but decoding requires both factors[6](https://dlmf.nist.gov/27.16).
Testing large integers for primality plays a major role in key generation in RSA and other public-key systems[16](https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-2.pdf). The practicality of constructing RSA ciphers depends on primality testing being easy to do, whereas the security of the cipher depends on the apparent difficulty of factoring large numbers[17](https://www.nationalacademies.org/read/2026/chapter/5).
**Quantum threat.** In 1994 [Peter Shor](https://www.edgepedia.org/peter-shor) discovered a quantum algorithm that could efficiently find the prime factors of large integers, running in polynomial time on a quantum computer[18](https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=934896). For large enough numbers, a conventional computer has been estimated to need billions of years to find the prime factors, while a sufficiently capable quantum computer could solve the puzzle in days or even hours[19](https://www.nist.gov/cybersecurity-and-privacy/what-post-quantum-cryptography). NIST released the first three finalized post-quantum cryptography standards in 2024, based on structured lattices and hash functions rather than factoring, and under its transition timeline will deprecate and ultimately remove quantum-vulnerable algorithms from its standards by 2035[19](https://www.nist.gov/cybersecurity-and-privacy/what-post-quantum-cryptography) • [20](https://csrc.nist.gov/Projects/Post-Quantum-Cryptography?source=post_page---------------------------).
## References
1. [Barry Mazur, "The Riemann Hypothesis," Clay Mathematics Institute public lecture](https://www.claymath.org/library/public_lectures/mazur_riemann_hypothesis.pdf)
2. [Prime Number, Wolfram MathWorld](https://mathworld.wolfram.com/PrimeNumber.html)
3. [Prime numbers, MacTutor History of Mathematics, University of St Andrews](https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/)
4. [Riemann's 1859 Manuscript, Clay Mathematics Institute](https://www.claymath.org/collections/riemanns-1859-manuscript/)
5. [Mersenne Prime Discovery, 2^136279841−1 is Prime, GIMPS](https://www.mersenne.org/primes/?press=M136279841)
6. [DLMF §27.16 Cryptography, NIST](https://dlmf.nist.gov/27.16)
7. [Twin Prime Conjecture, Wolfram MathWorld](https://mathworld.wolfram.com/TwinPrimeConjecture.html)
8. [Chapter 4 Prime Numbers, MATH1001, University of Southampton](https://www.southampton.ac.uk/~wright/1001/chapter-primes.html)
9. [Angela Reddick and Yeng Xiong, "The Search for One as a Prime Number," Furman University Electronic Journal of Undergraduate Mathematics 16 (2016)](https://scholarexchange.furman.edu/fuejum/vol16/iss1/1/)
10. [Riemann Hypothesis, Clay Mathematics Institute](https://www.claymath.org/millennium/riemann-hypothesis/)
11. [AMS Notices, April 2020, Cole Prize citation for James Maynard](https://www.ams.org/journals/notices/202004/202004FullIssue.pdf)
12. [Shijie Gu, "How 'small' can the gap be?," AMS Math Grad Blog, 2013](https://blogs.ams.org/mathgradblog/2013/06/24/small-gap-be-a-huge-landmark-number-theory/)
13. ["Prime Numbers: A...," AMS Notices, June/July 2015](https://www.ams.org/notices/201506/rnoti-p660.pdf)
14. [Twin Primes, Wolfram MathWorld](https://mathworld.wolfram.com/TwinPrimes.html)
15. [List of known Mersenne prime numbers, PrimeNet](https://www.mersenne.org/primes/)
16. [NIST Special Publication 800-2, Appendix L, Primality testing](https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-2.pdf)
17. [National Research Council, Probability and Algorithms, Chapter 4](https://www.nationalacademies.org/read/2026/chapter/5)
18. [Dustin Moody and Angela Robinson, "Cryptographic Standards in a Post-Quantum Era," NIST, 2022](https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=934896)
19. [What Is Post-Quantum Cryptography?, NIST](https://www.nist.gov/cybersecurity-and-privacy/what-post-quantum-cryptography)
20. [Post-Quantum Cryptography, NIST CSRC](https://csrc.nist.gov/Projects/Post-Quantum-Cryptography?source=post_page---------------------------)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Elementary number theory › Prime numbers: elementary aspects*
*Initially written Sep 17, 2026 · Reviewed: Sep 17, 2026; Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 11, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license