How did Euclid prove that there are infinitely many prime numbers?

In his work Elements, Euclid provided an elegant proof that there are infinitely many prime numbers. His argument, found in Proposition 20 of Book IX, demonstrates that no finite collection of primes can contain every prime number.1

To prove this, Euclid considered any finite set of primes, such as a, b, c, ..., n. He then constructed a new number, N, by multiplying these primes together and adding one:
$$N=(a\times b\times c\times \dots \times n)+1$$

Euclid then examined two possibilities:
* If N is prime: Since N is larger than any of the primes in the original set, it must be a new prime not included in that collection.1
* If N is composite: It must have a prime factor. Euclid demonstrated that this prime factor cannot be any of the primes in the original set, as dividing N by any of those primes would always leave a remainder of 1.1

In either case, the original finite set of primes can always be expanded to include at least one additional prime. Consequently, the collection of prime numbers must be infinite.1