Proving Infinitude of Primes

Intro to Proofs · Axiom Academy

EXAMPLE Proving the Infinitude of Primes Euclid's classic proof by contradiction — one of the most beautiful arguments in mathematics Prove that there are infinitely many prime numbers. We will work through Euclid's classic argument (c. 300 BCE): assume there are only finitely many primes, build a clever number from them, and show that this assumption forces a prime that the list left out. Excellent work — you have followed one of the most elegant proofs in mathematics. Here is what makes it brilliant: Proof by contradiction: we assume the opposite of what we want, then show it leads to an impossibility. The construction : this number leaves remainder 1 when divided by every prime on the assumed list, so none of them divides it. The dilemma: N is either prime or composite. Either way it produces a prime outside the list, contradicting the claim that the list held them all. N need not itself be prime: e.g. . The proof still works because 59 and 509 are new primes — that is why both cases are needed. Why it is airtight: every integer greater than 1 is prime or has a prime divisor (the Fundamental Theorem of Arithmetic). Dating back to Euclid around 300 BCE, this argument still underpins number theory and modern cryptography.

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