Square a5 · Mathematics · Queenside

Infinitude of primes

There are infinitely many prime numbers (p is prime).

Meaning

The formula asserts that for every natural number NN there exists a prime number pp strictly larger than NN. In other words, the set of primes is infinite: there is no largest prime, and the sequence of primes 2,3,5,7,11,…2,3,5,7,11,\ldots continues without end.

Euclid’s classical proof (Elements, Book IX, Proposition 20) proceeds by contradiction in constructive clothing. Given any finite list of primes p1,…,pkp_{1},\ldots,p_{k}, form N=p1p2⋯pk+1.N = p_{1}p_{2}\cdots p_{k}+1. Then N>1N>1, so NN has some prime factor qq. That factor qq cannot equal any pip_{i}, because each pip_{i} leaves remainder 11 when dividing NN. Hence there is always a prime outside any finite list.

Context

Euclid’s argument is one of the oldest surviving proofs of an infinitude result in mathematics. It does not produce the next prime explicitly, but it proves that no finite catalogue of primes can be complete. Later proofs give quantitative refinements: Euler showed that the harmonic series of reciprocals of primes diverges, ∑1/p=∞\sum 1/p=\infty, which again implies infinitude and links primes to analysis. Erdős gave an elegant elementary proof related to Euler’s idea. Dirichlet’s theorem on primes in arithmetic progressions vastly strengthens the qualitative statement: there are infinitely many primes congruent to aa modulo mm whenever gcd⁡(a,m)=1\gcd(a,m)=1.

The infinitude of primes is the qualitative companion to the prime number theorem (square a7), which describes how densely primes occur among the integers. Together they answer “are there enough primes?” and “how many up to xx?” Unique factorization (square a4) explains why primes matter; infinitude explains that the supply never runs out.

The result earns a square because it is elementary, ancient, and inexhaustible as a source of generalizations—from Dirichlet’s theorem to the twin prime conjecture and beyond. It is also a model of mathematical style: a short, decisive argument that settles a global question about an infinite set by a finite construction.

Sources