Euclid's Theorem

From ProofWiki
Jump to navigation Jump to search


Theorem

For any finite set of prime numbers, there exists a prime number not in that set.


In the words of Euclid:

Prime numbers are more than any assigned multitude of prime numbers.

(The Elements: Book $\text{IX}$: Proposition $20$)


Corollary 1

There are infinitely many prime numbers.


Corollary 2

There is no largest prime number.


Proof

Let $\mathbb P$ be a finite set of prime numbers.

Consider the number:

$\ds n_p = \paren {\prod_{p \mathop \in \mathbb P} p} + 1$


Take any $p_j \in \mathbb P$.

We have that:

$\ds p_j \divides \prod_{p \mathop \in \mathbb P} p$

Hence:

$\ds \exists q \in \Z: \prod_{p \mathop \in \mathbb P} p = q p_j$

So:

\(\ds n_p\) \(=\) \(\ds q p_j + 1\) Division Theorem
\(\ds \leadsto \ \ \) \(\ds n_p\) \(\perp\) \(\ds p_j\) Definition of Coprime Integers


So $p_j \nmid n_p$.


There are two possibilities:

$(1): \quad n_p$ is prime, which is not in $\mathbb P$.
$(2): \quad n_p$ is composite.

But from Positive Integer Greater than 1 has Prime Divisor‎, it must be divisible by some prime.

That means it is divisible by a prime which is not in $\mathbb P$.


So, in either case, there exists at least one prime which is not in the original set $\mathbb P$ we created.

$\blacksquare$


Historical Note

This proof is Proposition $20$ of Book $\text{IX}$ of Euclid's The Elements.


Fallacy

There is a fallacy associated with Euclid's Theorem.

It is often seen to be stated that: the number made by multiplying all the primes together and adding $1$ is not divisible by any members of that set.

So it is not divisible by any primes and is therefore itself prime.

That is, sometimes readers think that if $P$ is the product of the first $n$ primes then $P + 1$ is itself prime.

This is not the case.

For example:

$\left({2 \times 3 \times 5 \times 7 \times 11 \times 13}\right) + 1 = 30\ 031 = 59 \times 509$

both of which are prime, but, take note, not in that list of six primes that were multiplied together to get $30\ 030$ in the first place.


Also see


Source of Name

This entry was named for Euclid.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Euclid%27s_Theorem&oldid=712523"