Euclid's Proof of Infinite Primes: The Oldest Beautiful Proof

Terminology

What & Why

Around 300 BCE, Euclid proved that there are infinitely many prime numbers. This proof, found in Book IX of the Elements (Proposition 20), is often cited as the most beautiful proof in all of mathematics. It is short, elementary, and devastating in its logic.

The question seems simple: do the primes ever stop? As numbers get larger, primes become rarer. After 2, 3, 5, 7, 11, 13, the gaps between primes grow. Could there be a largest prime, after which every number is composite? Euclid showed this is impossible with an argument so clean that it has remained unchanged for over two thousand years.

This proof matters because it demonstrates the power of proof by contradiction, one of the most important techniques in mathematics and computer science. It also reveals a deep truth about the structure of numbers: primes are the "atoms" of arithmetic, and there are infinitely many of them. This fact underpins modern cryptography (RSA relies on the abundance of large primes), hash function design, and the entire field of number theory.

How It Works

Euclid's Argument

Assume, for contradiction, that there are only finitely many primes. List them all:

Now construct a new number N by multiplying all the primes together and adding 1:

Consider what happens when you divide N by any prime in the list. Since N = (p_1 \cdot p_2 \cdots p_k) + 1, dividing N by any p_i leaves a remainder of 1. So no prime in our list divides N.

But by the Fundamental Theorem of Arithmetic, N must have at least one prime factor. That prime factor is not in our list. This contradicts the assumption that we listed all primes. Therefore, the assumption is false: there are infinitely many primes.

A Common Misconception

A frequent misunderstanding: N itself does not have to be prime. In the example above, N = 30031 = 59 \times 509. The point is that N has a prime factor (59 or 509) that was not in the original list. The argument only requires that at least one new prime exists, not that N is prime.

Variations and Generalizations

Euclid's technique generalizes. For any finite set of primes S, the number (\prod_{p \in S} p) + 1 has a prime factor outside S. This means you can always extend any finite list of primes. The primes are inexhaustible.

The Prime Number Theorem quantifies how primes thin out:

The density of primes near n is approximately \frac{1}{\ln n}. They become rarer but never vanish.

Complexity Analysis

The growth rate of the n-th prime p_n is:

And the primorial p_k\# = p_1 \cdot p_2 \cdots p_k grows as:

by the Prime Number Theorem. So Euclid's constructed number N = p_k\# + 1 grows super-exponentially in k.

Implementation

ALGORITHM EuclidInfinityConstruction(knownPrimes)
INPUT: knownPrimes: a finite list of prime numbers
OUTPUT: a new prime not in the list
BEGIN
  product <- 1
  FOR EACH p IN knownPrimes DO
    product <- product * p
  END FOR

  N <- product + 1

  // Find a prime factor of N (which must be outside knownPrimes)
  newPrime <- SmallestPrimeFactor(N)
  RETURN newPrime
END

ALGORITHM SmallestPrimeFactor(n)
INPUT: n: a natural number > 1
OUTPUT: the smallest prime factor of n
BEGIN
  IF n MOD 2 = 0 THEN
    RETURN 2
  END IF

  d <- 3
  WHILE d * d <= n DO
    IF n MOD d = 0 THEN
      RETURN d
    END IF
    d <- d + 2
  END WHILE

  RETURN n  // n itself is prime
END

ALGORITHM SieveOfEratosthenes(limit)
INPUT: limit: upper bound for prime search
OUTPUT: list of all primes up to limit
BEGIN
  isPrime <- array of true values, indexed 0 to limit
  isPrime[0] <- false
  isPrime[1] <- false

  FOR i FROM 2 TO FLOOR(SQRT(limit)) DO
    IF isPrime[i] THEN
      FOR j FROM i*i TO limit STEP i DO
        isPrime[j] <- false
      END FOR
    END IF
  END FOR

  primes <- empty list
  FOR i FROM 2 TO limit DO
    IF isPrime[i] THEN
      APPEND i TO primes
    END IF
  END FOR

  RETURN primes
END

ALGORITHM GeneratePrimesEuclid(count)
INPUT: count: how many primes to generate
OUTPUT: a list of at least count primes
BEGIN
  primes <- [2]

  WHILE LENGTH(primes) < count DO
    newPrime <- EuclidInfinityConstruction(primes)
    IF newPrime NOT IN primes THEN
      APPEND newPrime TO primes
    END IF
  END WHILE

  RETURN primes
END

Real-World Applications

• RSA cryptography depends on the abundance of large primes: key generation requires finding two large primes (typically 1024+ bits each), which is feasible precisely because primes are infinite and sufficiently dense
• Hash table design uses prime-sized tables to minimize collision clustering; the infinitude of primes guarantees a suitable table size always exists
• Pseudorandom number generators (linear congruential generators) use prime moduli for maximum period length, relying on the availability of primes of any desired size
• Error-correcting codes (Reed-Solomon codes) operate over finite fields $\text{GF}(p^n)$ where $p$ is prime; the infinitude of primes ensures fields of any characteristic exist
• Primality testing algorithms (Miller-Rabin, AKS) are essential infrastructure for cryptographic key generation, TLS certificate creation, and secure communication protocols
• The distribution of primes (described by the Prime Number Theorem and the Riemann Hypothesis) influences the analysis of algorithms that depend on number-theoretic properties

Key Takeaways

• Euclid's proof (circa 300 BCE) shows there are infinitely many primes by contradiction: multiply all known primes and add 1 to get a number that must have a new prime factor
• The constructed number $N = p_1 \cdot p_2 \cdots p_k + 1$ is not necessarily prime itself; the key insight is that its prime factors cannot be in the original list
• This is the oldest known example of proof by contradiction, a technique that remains central to mathematics and theoretical computer science
• The Prime Number Theorem quantifies the density of primes: approximately $\frac{n}{\ln n}$ primes exist below $n$, so primes thin out but never vanish
• The infinitude of primes is essential for modern cryptography, hash function design, and error-correcting codes
• Euclid's proof exemplifies mathematical beauty: a profound truth established by an argument anyone can follow in a few lines