Infinitude of Primes

students, imagine you are trying to list every prime number that exists. You might start with $2$, then $3$, $5$, $7$, $11$, and keep going. A natural question appears: does this list ever end? The answer is no — there are infinitely many primes. This fact is one of the most important ideas in number theory 🔢✨

What you will learn

What it means for a set of numbers to be infinite in the context of primes.
Why prime numbers never run out.
How to use classic reasoning to prove there are infinitely many primes.
How this result connects to prime factorization and the Fundamental Theorem of Arithmetic.

What does “infinitely many primes” mean?

A prime number is a whole number greater than $1$ that has exactly two positive divisors: $1$ and itself. Examples include $2$, $3$, $5$, $7$, and $11$.

Saying there are infinitely many primes means there is no largest prime number. No matter how far you go, there is always another prime beyond the ones you already know.

This does not mean primes appear at regular intervals. In fact, the gaps between primes can become very large. For example, after $23$, the next prime is $29$, and after $89$, the next prime is $97$. Still, even if primes get less frequent, they never stop existing.

This idea is a key part of the broader study of prime numbers. Primes are like the “building blocks” of whole numbers because every whole number greater than $1$ can be broken into primes. If the prime building blocks ended, then number theory would look very different. But the list never ends 🌟

Euclid’s classic proof

The oldest and most famous proof that there are infinitely many primes comes from the Greek mathematician Euclid. His argument is simple, powerful, and elegant.

Step 1: Assume the opposite

Suppose, for the sake of argument, that there are only finitely many primes. Then we could list them all:

$$p_1, p_2, p_3, \dots, p_n$$

where these are every prime number that exists.

Step 2: Build a new number

Now form the number

$$N = p_1 p_2 p_3 \cdots p_n + 1$$

This number is one more than the product of all the primes on the list.

Step 3: Check divisibility

Now ask what happens if we divide $N$ by any prime $p_i$ from the list. Since $p_i$ divides the product $p_1 p_2 p_3 \cdots p_n$, the number $p_i$ also divides

$$N - 1 = p_1 p_2 p_3 \cdots p_n$$

But $N$ leaves remainder $1$ when divided by $p_i$, because

$$N = \left(p_1 p_2 p_3 \cdots p_n\right) + 1$$

So none of the primes in our supposed complete list divides $N$.

Step 4: Reach the contradiction

Every whole number greater than $1$ must have at least one prime divisor. That means $N$ must be divisible by some prime. But it is not divisible by any prime in the list. So either:

$N$ itself is prime, or
$N$ has a prime factor not in the list.

In either case, there exists a prime not included in our supposedly complete list. That is a contradiction.

So the assumption that there are only finitely many primes must be false. Therefore, there are infinitely many primes ✅

Why this proof works

The key idea is that if you multiply together every prime you know and then add $1$, the new number cannot be divided evenly by any of those primes.

This is a clever example of proof by contradiction. You assume the opposite of what you want to show, and then you find a logical problem that proves the assumption cannot be true.

students, this style of reasoning appears throughout mathematics. It is especially useful in number theory because divisibility rules can create strong conclusions from small observations.

Notice that Euclid’s proof does not tell us exactly what the next prime is. It only proves that some new prime must exist. For example, if you start with the primes $2$, $3$, and $5$, then

$$2 \cdot 3 \cdot 5 + 1 = 31$$

and $31$ is prime. If you start with $2$, $3$, $5$, and $7$, then

$$2 \cdot 3 \cdot 5 \cdot 7 + 1 = 211$$

and $211$ is also prime. But this does not always happen. Sometimes the number $N$ is composite, yet its prime factors are still new primes not in the original list. For example,

$$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1 = 2311$$

and $2311$ is prime, but in other cases similar expressions can factor into primes outside the list.

Connection to prime factorization

The infinitude of primes is closely connected to the Fundamental Theorem of Arithmetic, which says that every integer greater than $1$ can be written uniquely as a product of primes, up to the order of the factors.

For example,

$$84 = 2^2 \cdot 3 \cdot 7$$

This prime factorization uses primes $2$, $3$, and $7$.

Now think about what would happen if there were only finitely many primes. Then every whole number greater than $1$ would have to be built from just that limited set. But numbers keep growing and new prime factors keep appearing. Euclid’s proof shows that no finite list can contain them all.

This means prime factorization is not just a method for breaking numbers apart. It is also evidence that primes must keep going forever. If you can always create a number that forces a new prime factor, then the supply of primes cannot end.

Let’s look at a small example. Suppose someone claims the only primes are $2$, $3$, $5$, and $7$. Then their product is

$$2 \cdot 3 \cdot 5 \cdot 7 = 210$$

and

$$210 + 1 = 211$$

Since $211$ is not divisible by $2$, $3$, $5$, or $7$, it cannot be explained using only those primes. This shows the list was incomplete.

More ways to see the idea

Euclid’s proof is the most famous, but the idea of infinitude of primes can also be seen through other reasoning.

One simple fact is that if a number is composite, then it has a prime factor. So whenever you construct a number that avoids divisibility by a chosen set of primes, its prime factorization must introduce something new.

Here is the general pattern:

Start with any finite set of primes.
Multiply them together.
Add $1$.
The result is not divisible by any prime in the set.
Therefore, a new prime must exist.

This pattern can be repeated forever. No matter how many primes you list, there is always another one beyond them.

There are also other classic proofs, such as the one based on the number

$$2^n - 1$$

for suitable values of $n$, or proofs using factorials and divisibility. Even though these proofs look different, they all rely on the same central idea: you cannot trap all primes inside a finite box 📦

Why this matters in number theory

The infinitude of primes is not just a standalone fact. It is a foundation for many deeper ideas in number theory.

Because there are infinitely many primes, mathematicians can study patterns such as:

how often primes occur,
how far apart they can be,
how primes are distributed among the integers,
and how primes behave in modular arithmetic.

It also explains why prime factorization remains meaningful for all integers greater than $1$. Since new primes always exist, the set of prime factors available to build numbers is never exhausted.

In practical terms, primes are important in areas like computer science and cryptography. Many encryption methods rely on large prime numbers and the difficulty of factoring large products into primes. The fact that there are infinitely many primes guarantees that there will always be larger primes to use.

Conclusion

students, the lesson of infinitude of primes is simple to state but deep in meaning: there is no largest prime number. Euclid’s proof shows this by assuming there are only finitely many primes, building the number

$$p_1 p_2 p_3 \cdots p_n + 1$$

and then showing that this number forces a contradiction. The result is a cornerstone of number theory because it connects directly to prime factorization and the Fundamental Theorem of Arithmetic.

Every time you think you have reached the end of the prime numbers, mathematics gives you a way to go one step farther 🚀

Study Notes

A prime number is a whole number greater than $1$ with exactly two positive divisors: $1$ and itself.
“Infinitely many primes” means there is no largest prime.
Euclid’s proof assumes only finitely many primes exist and builds

$$N = p_1 p_2 p_3 \cdots p_n + 1$$

The number $N$ is not divisible by any prime in the assumed complete list.
Therefore, $N$ is either prime or has a prime factor not in the list.
This contradiction proves that there must be infinitely many primes.
The result is closely linked to the Fundamental Theorem of Arithmetic, which says every integer greater than $1$ has a unique prime factorization.
Infinitude of primes is a foundational idea in number theory and supports many advanced topics, including factorization, modular arithmetic, and cryptography.