Euclid's Proof

The Classical Argument

Euclid’s proof of the infinitude of primes is one of the earliest examples of a general argument in number theory. It does not depend on computation, experimentation, or knowledge of large primes. It proves that no finite list of primes can ever be complete.

Suppose we are given finitely many primes:

We do not yet assume that these are all primes. We merely ask whether this list could contain every prime.

Form the integer

This number is constructed to have a special property: when divided by any prime $p_i$ in the list, it leaves remainder $1$.

Indeed,

and each $p_i$ divides the product

Therefore

Hence no prime in the list divides $N$.

The Need for a Prime Divisor

Since

the integer $N$ has at least one prime divisor. This follows from the existence part of prime factorization.

Let $q$ be a prime such that

If the original list contained every prime, then $q$ would have to equal one of the listed primes. So

for some $i$.

But no $p_i$ divides $N$, because $N$ leaves remainder $1$ modulo $p_i$. This is impossible.

Therefore the original list cannot contain all primes.

Since every finite list of primes is incomplete, there must be infinitely many primes.

The Core Contradiction

The contradiction can be written compactly.

Assume

are all the primes. Set

Let $q\mid N$ be prime. Since $q$ appears in the list, $q=p_i$ for some $i$. Then

and

So $q$ divides their difference:

Thus

But no prime divides $1$. Contradiction.

Why $N$ Need Not Be Prime

A common misunderstanding is to think that Euclid’s proof constructs a new prime by making

prime. This is false.

The number $N$ may be composite.

For example,

and

The proof only requires that $N$ have some prime divisor. Since none of the listed primes divides $N$, any prime divisor of $N$ must be new.

The construction therefore produces a new prime indirectly, not necessarily as $N$ itself.

A Finite List Is Always Incomplete

Euclid’s proof works for any finite list of primes, even if the list is not ordered and even if it misses many small primes.

Given any finite list

the number

has a prime divisor outside the list.

Thus the theorem is stronger than the statement that primes do not stop at some largest prime. It says that no finite collection captures the entire set of primes.

This is a structural result about arithmetic, not merely a statement about large numbers.

The Role of Divisibility

The proof uses two elementary facts about divisibility.

First, if a prime $p_i$ divides the product

then adding $1$ produces a number not divisible by $p_i$.

Second, every integer greater than $1$ has a prime divisor.

The first fact constructs avoidance. The second fact forces the presence of a prime. Together they show that the new integer must point to a prime outside the original list.

This interaction between avoidance and existence appears often in number theory.

Consequences

Euclid’s theorem implies that primes are unbounded. For every integer $M$, there exists a prime $p$ such that

If not, then all primes would lie among the finitely many integers

That would give only finitely many primes, contradicting Euclid’s theorem.

Thus primes continue indefinitely.

Historical Importance

Euclid’s proof appears in the Elements, Book IX, Proposition 20. Its survival and influence come from its clarity. It begins with an arbitrary finite list, constructs a new number, and uses divisibility to force a contradiction.

Many later proofs in number theory follow a similar pattern: assume a finite obstruction, build an integer with carefully chosen congruence properties, and extract a prime divisor with unexpected behavior.

The proof is elementary, but its method is deep. It shows that the multiplicative structure of the integers cannot be generated by finitely many primes.