Euclid's proof of the infinitude of primes

From AoPSWiki

(Redirected from Euclid's proof on the infinitude of primes)

Euclid's proof of the infinitude of primes is a classic and well-known proof by the Greek mathematician Euclid that there are infinitely many prime numbers.

Proof

We proceed by contradiction. Suppose there are in fact only finitely many prime numbers, $p_1, p_2, p_3, \ldots, p_n$ . Let $N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$ . Since $N$ leaves a remainder of 1 when divided by any of our prime numbers $p_k$ , it is not divisible by any of them. However, the Fundamental Theorem of Arithmetic states that all positive integers have a unique prime factorization. Therefore, $N$ must have a prime factor (possibly itself) that is not among our set of primes, $\{p_1, p_2, p_3, \ldots, p_n\}$ . This means that $\{p_1, p_2, p_3, \ldots, p_n \}$ does not contain all prime numbers, which contradicts our original assumption. Therefore, there must be infinitely many primes.

Personal tools

Navigation

Search

Toolbox

Euclid's proof of the infinitude of primes

From AoPSWiki

Proof

See Also