gen-define-the-infinitude-of-primes-and-give-one-short-worked-ex-b860

Define the infinitude of primes and give one short worked example.

# Infinitude of Primes **Definition**: There are infinitely many prime numbers. That is, the sequence of primes 2, 3, 5, 7, 11, 13, ... never ends. ## Worked Example: Euclid's Proof **Proof by contradiction:** Assume there are only finitely many primes. Let's say they are: p₁, p₂, p₃, ..., pₙ Now consider the number: **N = (p₁ × p₂ × p₃ × ... × pₙ) + 1** For a concrete example, suppose all primes were just {2, 3, 5, 7}: - N = (2 × 3 × 5 × 7) + 1 = 210 + 1 = **211** Now, N is either prime or composite: - If **N is prime**, we found a new prime not in our original list (211 is indeed prime) - If **N is composite**, it must be divisible by some prime p. But dividing N by any prime in our list {2, 3, 5, 7} leaves remainder 1, so p cannot be in our list—meaning we found a new prime Either way, our assumption was wrong. Therefore, there are **infinitely many primes**. ∎