Euclid's Theorem/Corollary 1
Corollary to Euclid's Theorem
There are infinitely many prime numbers.
Proof 1
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$
Proof 2
Assume that there are only finitely many prime numbers.
Let $p$ be the largest of these.
Then from Existence of Prime between Prime and Factorial there exists a prime number $q$ such that:
- $p < q \le p! + 1$
So there cannot be such a $p$.
$\blacksquare$
Also known as
This result is often referred to as Euclid's Theorem.
But Euclid himself did not explicitly state that there is an infinite number of primes, just that it was impossible to create a list containing them all.
Some sources refer to it as Euclid's second theorem, his first being Euclid's Lemma for Prime Divisors.
Sources
- 1971: Allan Clark: Elements of Abstract Algebra ... (previous) ... (next): Chapter $1$: Properties of the Natural Numbers: $\S 22 \gamma$
- 1979: G.H. Hardy and E.M. Wright: An Introduction to the Theory of Numbers (5th ed.) ... (previous) ... (next): $\text I$: The Series of Primes: $1.4$ The sequence of primes
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): prime