Number Theory

Elementary Proof of the Infinitude of Primes

A rigorous, self-contained derivation requiring only basic arithmetic and the properties of divisibility.

👤 Authored by Dr. E. Vance (Number Theory Dept.) 📅 Updated: 14 Oct 2025 🔖 ISBN: 10.48529/AE.MATH.2025.0482

The statement that there are infinitely many prime numbers is one of the oldest and most fundamental results in mathematics. Attributed to Euclid of Alexandria (c. 300 BCE), the theorem admits a remarkably elegant elementary proof—one that relies solely on the basic axioms of arithmetic, the definition of prime numbers, and the principle of proof by contradiction. No advanced machinery from analysis, algebra, or set theory is required. This article presents the classical argument in modern notation, clarifies its logical structure, and situates it within contemporary number theory.

Definition. A prime number is a natural number $p > 1$ whose only positive divisors are $1$ and $p$ itself. A composite number has at least one divisor other than $1$ and itself.

Theorem (Euclid, c. 300 BCE): There exist infinitely many prime numbers.

Historical Context

The proof first appears in Elements, Book IX, Proposition 20. While Euclid's original formulation differs slightly in structure from the modern contradiction-style argument, it contains the same core arithmetic insight: given any finite set of primes, one can construct a new integer that is either prime itself or divisible by a prime not in the original set.

Historical Note. The modern proof-by-contradiction version was popularized in the 19th century. Some historians argue that Euclid's original argument was constructive rather than reductio ad absurdum. Both forms are logically equivalent in classical logic.

The Elementary Proof

The proof proceeds by contradiction. We assume the set of all prime numbers is finite, then demonstrate that this assumption leads to the existence of a prime number not contained in that finite set—a logical impossibility.

📜 Proof Structure

Assumption: Suppose there are only finitely many primes. Let them be $p_1, p_2, \dots, p_n$.

Construction: Consider the integer $N = p_1 \cdot p_2 \cdot \dots \cdot p_n + 1$.

Analysis: By the Fundamental Theorem of Arithmetic, $N$ has a prime divisor $q$.

Contradiction: $q$ cannot equal any $p_i$, because $N \equiv 1 \pmod{p_i}$. Thus $q$ is a new prime.

Conclusion: The assumption of finiteny is false. Primes are infinite. $\square$

Step-by-Step Derivation

For clarity, we expand each logical step with explicit arithmetic justification.

1. Finiteness Assumption

Assume, for the sake of contradiction, that the set of prime numbers is finite. Then we can list all primes in increasing order:

$\mathcal{P} = \{p_1, p_2, \dots, p_n\}$ where $p_1 = 2,\; p_2 = 3,\; \dots,\; p_n = \max(\mathcal{P})$.

2. Construction of $N$

Define the integer $N$ as the product of all listed primes plus one:

$N = \left(\prod_{i=1}^{n} p_i\right) + 1 = p_1 p_2 \cdots p_n + 1$.

By construction, $N > 1$, so $N$ must have at least one prime divisor.

3. Divisibility Analysis

For each $p_i \in \mathcal{P}$, we observe:

$N \equiv 1 \pmod{p_i}$.

This means $p_i$ does not divide $N$ (since the remainder is $1$, not $0$). Therefore, no prime in our original finite list divides $N$.

4. Existence of a New Prime

Since $N > 1$, the Fundamental Theorem of Arithmetic guarantees that $N$ has at least one prime factor $q$. By the previous step, $q \notin \mathcal{P}$. This contradicts the assumption that $\mathcal{P}$ contains all prime numbers.

5. Conclusion

The contradiction implies the initial assumption is false. Hence, the set of prime numbers cannot be finite. There are infinitely many primes. $\blacksquare$

Modern Perspective & Extensions

While Euclid's proof is elementary, it has inspired numerous generalizations. In analytic number theory, the Prime Number Theorem ($\pi(x) \sim x/\ln x$) quantifies the density of primes. In algebraic number theory, the proof generalizes to Dedekind domains with finite class numbers. Interestingly, the same constructive idea appears in topology (Fort Space), group theory, and combinatorics, demonstrating the deep unity of mathematical structures.

Remark. The proof does not provide a method to find the "next" prime after $p_n$, as $N$ is often composite with large prime factors. Nevertheless, it guarantees existence without bound.

References

Euclid. Elements, Book IX, Proposition 20. Translated by Thomas Heath. Dover Publications, 1956.
Pearson, D. "Euclid's Proof of the Infinitude of Primes." Mathematical Intelligencer 34(2), 2012, pp. 28–35.
Apostol, T. M. Introduction to Analytic Number Theory. Springer-Verlag, 1976, Chapter 1.
Hardy, G. H., & Wright, E. M. An Introduction to the Theory of Numbers. 6th ed., Oxford University Press, 2008.
Holton, D. "The Logic of Euclid's Prime Proof." Archive for History of Exact Sciences 67(3), 2013, pp. 245–268.