Course contentsShow
← Mathematics
Lesson 2722 of 3,12154. Number TheoryFree lesson

Infinitude of Primes: Euclid's Proof

Understand Euclid's elegant proof by contradiction that there are infinitely many prime numbers.

Infinitude of Primes: Euclid's Proof

What you'll learn: You'll understand one of mathematics' most elegant proofs—that there are infinitely many prime numbers—using nothing but simple logic and contradiction.

The Core Idea

Euclid's proof (from around 300 BCE) is a masterpiece of mathematical reasoning. It uses proof by contradiction: we assume the opposite of what we want to prove, then show this leads to an impossibility.

The Proof Step-by-Step

Assume there are only finitely many primes. Let's call them p₁, p₂, p₃, ..., pₙ (a complete list of every prime that exists).

Now consider this clever number: N = (p₁ × p₂ × p₃ × ... × pₙ) + 1

This is the product of ALL primes, plus one.

What can we say about N?

  • Either N is prime itself, OR
  • N is composite (has prime divisors)

Case 1: If N is prime, we've found a new prime not in our original list (since N is clearly larger than any pᵢ). Contradiction!

Case 2: If N is composite, it must be divisible by some prime. But when you divide N by any prime pᵢ from our list, you get remainder 1 (because N is one more than a multiple of each pᵢ). So N isn't divisible by ANY prime in our supposedly complete list. This means there must be some other prime that divides N. Contradiction again!

The Beautiful Conclusion

Either way, our assumption that there are finitely many primes leads to contradiction. Therefore, there must be infinitely many primes.

Key Takeaway: Euclid's proof elegantly shows that no finite list can contain all primes—you can always construct a number that requires a prime outside your list, proving primes are infinite.