Infinity of Primes

Intro to Proofs · Axiom Academy

Euclid's proof, around 300 BCE, that no finite list can hold every prime number. Prove that there are infinitely many prime numbers. We will argue by contradiction: assume the primes form a finite list , build the number , and show it forces a prime outside the list. Nice work — you walked through one of the most elegant proofs in all of mathematics. Here is what makes it tick: Proof by contradiction: assume the opposite of the goal, then show it forces a logical impossibility. The construction: is engineered so that dividing by any listed prime leaves remainder 1 — so no listed prime divides it. Prime factors exist: every integer greater than 1 is prime or has a prime factor, so N must hand us a prime — and it cannot be one already on the list. N need not be prime: e.g. . The new prime can be a factor of N , not N itself — the proof only needs one prime outside the list. Always one more: whatever finite list you start with, the same trick produces a prime it missed — so the primes never run out. Proof by contradiction shows up everywhere — from the irrationality of to Cantor's diagonal argument. Master it here and you have a tool for the rest of mathematics.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.