Euclid's Theorem/Corollary 1/Proof 1

From ProofWiki
Jump to navigation Jump to search

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