Euclid's Proof of Infinite Primes

Number Theory · Axiom Academy

LESSON Euclid's Proof of Infinite Primes One of the most elegant proofs in mathematics: there are infinitely many prime numbers A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, ... This means that no matter how many primes we list, there will always be more primes beyond our list. The sequence of primes never ends! 2. Proof by Contradiction: The Assumption To prove there are infinitely many primes, we'll use proof by contradiction . We assume the opposite of what we want to prove, and show this leads to a logical impossibility. Assumption (for contradiction): Suppose there are only finitely many prime numbers. Then we can list them all: Let's say the complete list of all primes is: p₁, p₂, p₃, ..., pₙ, where n is some finite number. For example, if there were only 5 primes, our list might be 2, 3, 5, 7, 11 . 3. Euclid's Clever Construction Here's Euclid's brilliant insight: Consider a new number N, defined as the product of all these primes, plus 1: For example, if our complete list were 2, 3, 5 , then: N = (2 × 3 × 5) + 1 = 30 + 1 = 31 This number N has a very special property, which we'll explore next... Now we examine how N relates to each prime in our supposed complete list. Let's pick any prime pᵢ from our list and try to divide N by it: When we divide N by any prime pᵢ in our list, we get: N ÷ pᵢ = (p₁ · p₂ · ... · pₙ + 1) ÷ pᵢ

This is the written version of the interactive lesson above. See the full Number Theory course.