There are infinitely many prime numbers. Euclid’s proof shows this with a short but very powerful idea: no finite list of primes can ever contain them all. If someone claims to have listed every prime, Euclid’s method builds a number that forces a new prime to appear.
A prime number is a whole number greater than 1 that has exactly two positive divisors: 1 and itself. Numbers such as 2, 3, 5, 7, 11, and 13 are prime. A composite number, such as 12 or 21, can be divided by smaller whole numbers other than 1.
Euclid’s proof is not just an old math fact. It explains something central about prime numbers: primes do not run out. No matter how far you count, there is always another prime somewhere beyond the ones you already know.
The Main Idea
Euclid begins by asking us to imagine the opposite of what we want to prove. Suppose there are only finitely many primes. That means we could write them all in one complete list:
p1, p2, p3, …, pn
Now multiply all of those primes together and add 1:
N = p1 × p2 × p3 × … × pn + 1
This new number N leaves a remainder of 1 when divided by any prime in the list. That is the central move. Every listed prime divides the product exactly, but after adding 1, none of them can divide the new number evenly.
So N is either prime itself, or it is composite and has prime divisors. Either way, those prime divisors cannot be any of the primes in the original list. That means the original list was not complete.
Euclid’s Proof Step by Step
1. Assume there are only finitely many primes
Start by assuming that all prime numbers can be listed. This is called a proof by contradiction. We temporarily accept the opposite claim and test whether it can survive logical pressure.
2. Multiply all listed primes
If the list contains every prime, multiply them together:
P = p1 × p2 × … × pn
This product is divisible by every prime in the list because each one is a factor of the product.
3. Add one to the product
Now form a new number:
N = P + 1
This is where the proof becomes sharp. When N is divided by any listed prime, the remainder is always 1. So none of the listed primes divides N.
4. Use the fact that every number has a prime divisor
Every whole number greater than 1 is either prime or can be broken down into prime factors. Therefore, N must have at least one prime divisor.
But that prime divisor is not in the original list. This contradicts the claim that the list contained all primes.
5. Reject the finite-prime assumption
The assumption leads to an impossible result. So the assumption must be false. Therefore, there are infinitely many prime numbers.
A Simple Example
Imagine someone claims that the only primes are:
2, 3, and 5
Multiply them and add 1:
2 × 3 × 5 + 1 = 31
The number 31 is prime, and it is not in the list. So the list was incomplete.
Now try a larger list:
2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031
This number is not prime. In fact:
30031 = 59 × 509
This matters because it clears up a common mistake. Euclid’s proof does not say the product of listed primes plus 1 is always prime. It says that this number has a prime divisor that is not on the original list.
Why the Proof Works
The proof works because divisibility is exact. If a prime number divides a product, then adding 1 creates a remainder. For any listed prime p, the product P is divisible by p. So:
P = multiple of p
But:
P + 1 = multiple of p + 1
That means P + 1 cannot be divisible by p. This applies to every prime in the supposed complete list.
The contradiction is unavoidable. A number greater than 1 must have a prime factor, but none of the listed primes can be that factor. So another prime exists.
What Euclid Actually Proved
Euclid proved that prime numbers are not limited to a final largest prime. The proof does not tell us where the next prime is, and it does not give a fast method for finding all primes. Its purpose is different.
It proves a structural truth: the set of prime numbers is infinite.
| Question | Answer |
|---|---|
| Does it prove infinitely many primes exist? | Yes. |
| Does it find the next prime after a given number? | No. |
| Is the product of primes plus 1 always prime? | No. |
| Does the new number always have a new prime factor? | Yes. |
Common Misunderstanding: Product Plus One
Many explanations stop after saying “multiply the primes and add 1.” That can make it sound as if the new number must always be prime. It does not.
The correct statement is more careful:
If you multiply any finite list of primes and add 1, the result is not divisible by any prime in that list.
The result may be prime, or it may be composite. If it is composite, its prime factors are still outside the original list. That is enough to prove that the list did not contain every prime.
This distinction makes Euclid’s proof stronger, not weaker. The proof does not depend on luck. It works whether the new number is prime or composite.
Connection to Prime Factorization
Euclid’s proof depends on a basic fact about whole numbers: every integer greater than 1 has at least one prime divisor. This idea is closely related to prime factorization, where a composite number is written as a product of primes.
For example:
84 = 2 × 2 × 3 × 7
The number 84 is not prime, but its structure is built from primes. In this sense, primes act as the irreducible pieces of multiplication. Euclid’s proof shows that there are endlessly many such pieces.
When checking whether a number is prime, this idea also matters. You do not need to test every smaller number. You only need to test divisibility up to the square root of the number, because any larger factor would need a smaller partner. For quick testing, you can use the Prime Number Checker to see whether a number is prime and connect the result back to the logic behind divisibility.
Why Infinite Primes Matter
The infinity of primes is one of the first deep facts in number theory. It shows that prime numbers are not just scattered entries in a table. They form an endless sequence with patterns, gaps, surprises, and open questions.
This result supports many later ideas, including:
- Prime factorization: breaking composite numbers into prime factors.
- Greatest common divisors: comparing numbers through shared prime factors.
- Modular arithmetic: studying remainders after division.
- Prime gaps: measuring spaces between consecutive primes.
- Cryptography: using large primes in secure digital systems.
Modern mathematics goes far beyond Euclid’s original argument, but the proof remains one of the cleanest demonstrations of mathematical reasoning. It starts with a simple assumption and ends by showing that the assumption cannot be true.
Euclid’s Proof in Plain Language
Suppose you think you have all the primes. Multiply them together. Then add 1.
The new number cannot be divided evenly by any prime from your list, because each division leaves a remainder of 1. But the new number must either be prime or have prime factors. So at least one prime exists outside your list.
That means no list of primes can ever be final.
There is always another prime.
FAQ
What is Euclid’s proof of infinite primes?
Euclid’s proof shows that prime numbers never end. It assumes there is a finite list of all primes, multiplies them together, adds 1, and shows that the new number must have a prime divisor outside the original list.
Does Euclid’s proof mean the product of primes plus 1 is always prime?
No. The product of primes plus 1 can be prime or composite. The important point is that none of the primes in the original list divides it. If it is composite, its prime factors must include a prime outside the list.
Why does adding 1 matter in Euclid’s proof?
Adding 1 makes the new number leave a remainder of 1 when divided by any prime in the original list. This prevents every listed prime from being a divisor of the new number.
What type of proof is Euclid’s infinite primes proof?
It is commonly written as a proof by contradiction. It begins by assuming that only finitely many primes exist, then shows that this assumption creates a logical contradiction.
Does Euclid’s proof help find very large primes?
Not directly. Euclid’s proof proves that infinitely many primes exist, but it is not designed as a fast prime-search method. Modern prime testing uses more specialized algorithms.
Why is Euclid’s proof still important?
It remains important because it gives a clear reason why primes cannot run out. It also connects directly to divisibility, prime factorization, and the logic behind many later topics in number theory.