# 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:

$$
p_1,p_2,\ldots,p_k.
$$

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

Form the integer

$$
N=p_1p_2\cdots p_k+1.
$$

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

Indeed,

$$
N=p_1p_2\cdots p_k+1
$$

and each $p_i$ divides the product

$$
p_1p_2\cdots p_k.
$$

Therefore

$$
N\equiv1\pmod{p_i}.
$$

Hence no prime in the list divides $N$.

## The Need for a Prime Divisor

Since

$$
N>1,
$$

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

$$
q\mid N.
$$

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

$$
q=p_i
$$

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

$$
p_1,p_2,\ldots,p_k
$$

are all the primes. Set

$$
N=p_1p_2\cdots p_k+1.
$$

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

$$
q\mid p_1p_2\cdots p_k
$$

and

$$
q\mid N.
$$

So $q$ divides their difference:

$$
N-p_1p_2\cdots p_k=1.
$$

Thus

$$
q\mid1.
$$

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

$$
N=p_1p_2\cdots p_k+1
$$

prime. This is false.

The number $N$ may be composite.

For example,

$$
2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031,
$$

and

$$
30031=59\cdot509.
$$

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

$$
p_1,\ldots,p_k,
$$

the number

$$
p_1\cdots p_k+1
$$

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

$$
p_1p_2\cdots p_k,
$$

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

$$
p>M.
$$

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

$$
2,3,\ldots,M.
$$

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.