Prime Numbers

Definition & Properties

Examples

In Depth

Prime numbers are the atoms of arithmetic — every integer greater than 1 is either prime or a unique product of primes. The Prime Number Theorem (PNT), proved independently by Hadamard and de la Vallée Poussin in 1896, gives the asymptotic density: \(\pi(x)\sim x/\ln x\), meaning primes thin out logarithmically.

The distribution of primes is deeply connected to the Riemann zeta function. The Riemann Hypothesis — that all non-trivial zeros of \(\zeta(s)\) lie on the line \(\text{Re}(s)=1/2\) — would give the sharpest known error term in the PNT. It remains unproved and is one of the Millennium Prize Problems.

Primality testing is computationally easy: the AKS algorithm (2002) runs in polynomial time. Factoring, however, is believed to be hard — the security of RSA encryption rests on this asymmetry. The largest known prime (as of 2024) is a Mersenne prime with over 41 million digits.

Further Reading & Context

The infinitude of primes was proved by Euclid: if \(p_1,\ldots,p_k\) were all primes, then \(p_1\cdots p_k+1\) is divisible by a prime not in the list. Euler's proof uses the divergence of \(\sum 1/p\): if there were finitely many primes, \(\prod_p(1-p^{-1})^{-1}=\zeta(1)\) would converge, contradicting the divergence of the harmonic series.

Dirichlet's theorem: for \(\gcd(a,q)=1\), there are infinitely many primes \(p\equiv a\pmod{q}\), and they are equidistributed among the \(\phi(q)\) residue classes. The proof uses Dirichlet \(L\)-functions and is a cornerstone of analytic number theory.

Prime gaps: the average gap between consecutive primes near \(N\) is \(\ln N\). Bertrand's postulate (proved by Chebyshev): for every \(n\geq1\), there is a prime between \(n\) and \(2n\). The prime number theorem implies gaps of size \(O(\ln N)\) on average; the largest known gaps are consistent with Cramér's conjecture \(O((\ln N)^2)\).

Primality testing: the AKS algorithm (2002) proves primality deterministically in polynomial time \(O(\log^{6+\epsilon}n)\). In practice, the Miller–Rabin probabilistic test (with multiple witnesses) is faster and used in cryptographic libraries. The BPSW test (combining Miller–Rabin and Lucas) has no known counterexamples.

Primes in nature and technology: prime numbers appear in cicada life cycles (13 and 17 years, both prime — possibly to avoid synchronization with predators), in the design of hash tables (prime table sizes reduce collisions), and in error-correcting codes (Reed–Solomon codes over prime fields).