Euclid's Theorem/Corollary 1

From ProofWiki
Jump to navigation Jump to search

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