# Infinitude of Primes

## The Basic Question

Prime numbers are the building blocks of the positive integers. Once unique prime factorization is known, a natural question arises: are there only finitely many primes, or do primes continue forever?

The answer is that there are infinitely many primes.

This result is one of the oldest theorems in number theory. Its proof is short, but the idea is powerful: any finite list of primes can be used to construct an integer that forces the existence of another prime.

## Euclid's Theorem

There are infinitely many prime numbers.

Suppose, for contradiction, that there are only finitely many primes. List them as

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

Now form the integer

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

The integer $N$ is greater than $1$, so by unique prime factorization it has at least one prime divisor. Let $q$ be a prime such that

$$
q\mid N.
$$

Since $q$ is prime, it must be one of the primes in the list. Thus

$$
q=p_i
$$

for some $i$.

But $p_i$ divides the product

$$
p_1p_2\cdots p_k.
$$

It also divides $N$. Therefore $p_i$ divides their difference:

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

Hence

$$
p_i\mid 1,
$$

which is impossible for a prime $p_i>1$.

This contradiction shows that no finite list can contain all primes. Therefore there are infinitely many primes.

## The Constructive Idea

The proof does not say that

$$
p_1p_2\cdots p_k+1
$$

must itself be prime. It only says that it has a prime divisor not already in the list.

For example, using the primes

$$
2,3,5,7,11,13,
$$

we form

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

This number is not prime, since

$$
30031=59\cdot509.
$$

But both $59$ and $509$ are primes not in the original list. That is exactly what the proof needs.

The argument produces a new prime indirectly through divisibility.

## Why the Remainder Is Important

The key property of $N$ is that it leaves remainder $1$ when divided by each prime in the list:

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

for every $i$.

Thus no listed prime divides $N$. Since every integer greater than $1$ has a prime divisor, $N$ must have a prime divisor outside the list.

This is a typical number-theoretic argument. We build an integer with a prescribed divisibility pattern and then use factorization to force a conclusion.

## Infinitude Beyond All Bounds

Euclid's theorem implies that primes are unbounded. For every number $M$, there exists a prime greater than $M$.

Indeed, suppose all primes were at most $M$. Then there would be only finitely many of them, since there are only finitely many positive integers less than or equal to $M$. This would contradict the infinitude of primes.

Thus primes do not merely occur infinitely often as an abstract set. They occur beyond every finite bound.

## A Variant Proof Using Factorials

There is another common proof using factorials.

Let $n\ge2$. Consider

$$
n!+1.
$$

For every integer $k$ with

$$
2\le k\le n,
$$

we have

$$
n!\equiv0\pmod{k}.
$$

Therefore

$$
n!+1\equiv1\pmod{k}.
$$

So none of the integers

$$
2,3,\ldots,n
$$

divides $n!+1$.

Since $n!+1>1$, it has a prime divisor $q$. This prime divisor cannot satisfy $q\le n$, because then $q$ would divide $n!+1$, contradicting the remainder calculation.

Hence

$$
q>n.
$$

Since $n$ was arbitrary, there are primes larger than every integer $n$.

## Relation to Unique Factorization

The proof of the infinitude of primes uses the fact that every integer greater than $1$ has a prime divisor. This is the existence part of unique prime factorization.

It does not require the full uniqueness statement. However, the theorem fits naturally after prime factorization because primes are then understood as the irreducible components of integers.

Once every integer decomposes into primes, it becomes unavoidable to ask whether the supply of such components is finite or infinite.

## Infinitely Many Primes in Special Classes

Euclid's theorem proves that primes are infinite in total. A deeper question asks whether infinitely many primes occur in special arithmetic classes.

For example, are there infinitely many primes congruent to $1$ modulo $4$? Are there infinitely many primes congruent to $3$ modulo $4$? More generally, if

$$
\gcd(a,m)=1,
$$

are there infinitely many primes of the form

$$
a+mk?
$$

Dirichlet's theorem on arithmetic progressions answers yes. This theorem belongs to analytic number theory and requires tools far beyond Euclid's argument.

Euclid's theorem is therefore the first member of a much larger family of questions about the distribution of primes.

## Role in Number Theory

The infinitude of primes shows that arithmetic has no finite list of basic multiplicative atoms. No matter how many primes are known, more primes remain.

This fact is foundational for prime distribution, analytic number theory, algebraic number theory, and cryptography. It also marks the beginning of a recurring theme: primes are simple to define but difficult to understand in their global behavior.

The proof itself is a model of number-theoretic reasoning. It combines contradiction, divisibility, remainders, and prime factorization in a compact argument that continues to influence modern mathematics.