Definition & Notation

In mathematics, a prime number (or simply prime) is a natural number \( n > 1 \) that cannot be formed by multiplying two smaller natural numbers. Equivalently, a prime has exactly two distinct positive divisors: 1 and \( n \) itself. Numbers greater than 1 that are not prime are called composite numbers. The number 1 is neither prime nor composite by convention[1].

The set of prime numbers is commonly denoted by \( \mathbb{P} \). The first few primes are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...

Every integer greater than 1 is either a prime number or can be uniquely expressed as a product of primes, a result known as the Fundamental Theorem of Arithmetic[2].

Historical Development

Interest in prime numbers dates back to ancient civilizations. The Rhind Mathematical Papyrus (c. 1650 BCE) demonstrates early Egyptian understanding of number properties. The Greeks formalized the study, with Euclid proving in his Elements (Book IX, Proposition 20) that there are infinitely many primes using a brilliant contradiction argument[3].

In the 3rd century BCE, Eratosthenes devised the Sieve of Eratosthenes, an efficient algorithm for finding all primes up to a given limit. Centuries later, Carl Friedrich Gauss and Adrien-Marie Legendre independently formulated the Prime Number Theorem, describing the asymptotic distribution of primes[4].

Historical Note The modern definition excluding 1 from primes was standardized in the early 20th century to preserve the uniqueness clause in the Fundamental Theorem of Arithmetic.

Key Properties

  • Uniqueness of 2: 2 is the only even prime number. All other primes are odd.
  • Goldbach's Conjecture: Every even integer greater than 2 can be expressed as the sum of two primes. Verified computationally up to \(4 \times 10^{18}\), but unproven[5].
  • Twin Primes: Pairs of primes differing by 2 (e.g., (3,5), (11,13), (17,19)). The Twin Prime Conjecture posits infinitely many such pairs.
  • Mersenne Primes: Primes of the form \( M_p = 2^p - 1 \) where \( p \) itself is prime. Only 52 Mersenne primes are known as of 2025.

Distribution & Theorems

While primes appear irregularly among integers, their overall density follows precise asymptotic laws. The Prime Number Theorem (PNT), proven independently by Hadamard and de la Vallée Poussin in 1896, states:

\pi(x) \sim \frac{x}{\ln x} \quad \text{as } x \to \infty

where \( \pi(x) \) counts primes \( \leq x \). This implies the probability that a randomly chosen number near \( x \) is prime is approximately \( 1/\ln x \).

Deeper structure is captured by the Riemann Hypothesis, which concerns the zeros of the Riemann zeta function \( \zeta(s) \). If true, it would provide the tightest possible bound on prime distribution errors. It remains one of the Millennium Prize Problems[6].

Modern Applications

Primes transitioned from pure mathematics to practical technology in the late 20th century:

  • Cryptography: RSA encryption relies on the computational difficulty of factoring large semiprimes (products of two large primes). Modern key sizes use primes with 1536+ bits.
  • Hash Functions: Prime moduli reduce collision rates in hash tables and cryptographic checksums.
  • Pseudorandom Generation: Linear congruential generators and cryptographic PRNGs use prime parameters for optimal period lengths.
  • Distributed Systems: Prime number sequences optimize load balancing and consensus algorithms (e.g., Paxos variants).

Largest Known Primes

The search for large primes is coordinated by the Great Internet Mersenne Prime Search (GIMPS), a volunteer computing network. As of 2025, the largest known prime is:

2^{82,589,933} - 1 \quad \text{(24,862,048 digits)}

Discovered in December 2018 by Patrick Laroche via GIMPS. All largest known primes since 1952 have been Mersenne primes due to the efficiency of the Lucas–Lehmer primality test for this specific form[7].

References & Further Reading

  1. Weisstein, E.W. "Prime Number." MathWorld, Wolfram Research. 2023.
  2. Hardy, G.H. & Wright, E.M. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, 2008.
  3. Euclid. Elements, Book IX, Proposition 20. Translated by Heath, T.L. Cambridge UP, 1926.
  4. Edwards, H.M. Prime Numbers: A Computational Perspective. Springer, 2016.
  5. Olivier R. & Wu, H. "Computational Verification of Goldbach's Conjecture to \(4 \times 10^{18}\)." Math. Comp. 89(322), 2020.
  6. Edwards, H.M. Riemann's Zeta Function. Dover Publications, 2001.
  7. GIMPS Project. "Great Internet Mersenne Prime Search." mersenne.org. Accessed Nov 2025.

Related Topics

Number Theory

Branch of mathematics studying integers and integer-valued functions.

RSA Cryptography

Public-key encryption system based on prime factorization difficulty.

Riemann Hypothesis

Conjecture about the zeros of the Riemann zeta function and prime distribution.