Euclid's Theorem/Corollary 1/Proof 1
Corollary to Euclid's Theorem
There are infinitely many prime numbers.
Proof
Assume that there are only finitely many prime numbers, and that there is a grand total of $n$ primes.
Then it is possible to define the set of all primes:
- $\mathbb P = \set {p_1, p_2, \ldots, p_n}$
From Euclid's Theorem, however, we can always create a prime which is not in $\mathbb P$.
So we can never create a finite list of all the primes, because we can guarantee to construct a number which has prime factors that are not in this list.
Thus, there are infinitely many prime numbers.
$\blacksquare$
Source of Name
This entry was named for Euclid.
Historical Note
This Corollary 1 to Euclid's Theorem is itself often referred to as Euclid's Theorem, although Euclid himself never raised the concept of infinity.
Strictly speaking, Euclid's Theorem merely states that from any finite set of prime numbers, it is always possible to demonstrate that there exists another not in that list.
Sources
- 1969: C.R.J. Clapham: Introduction to Abstract Algebra ... (previous) ... (next): Chapter $3$: The Integers: $\S 13$. Unique Factorisation: Theorem $23$
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): Chapter $2$: Some Properties of $\Z$: Exercise $2.15$
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$: Theorem $5$