📂Number Theory

Euclid's Proof: There are Infinitely Many Primes

Theorem ¹

Prime numbers exist infinitely.

Explanation

There are several methods to prove that prime numbers are infinite. Among them, the simplest is Euclid’s method. This proof is not only simple but also famously elegant.

Proof

Assume that there are $n$ prime numbers. Let’s call these primes $p_1, p_2, \cdots , p_n$ and consider $p_{n+1}=p_1 p_2 \cdots p_n + 1$.

• If $p_{n+1}$ is a prime number, then $p_{n+1}$ is a new prime number that is not equal to any other prime numbers. This contradicts the assumption.
• If $p_{n+1}$ is not a prime number, then $p_{n+1}$ can be expressed as a product of prime numbers $q_1, q_2, \cdots , q_m$. However, since $q_1$ is also a prime number, it is not equal to any of $p_1, p_2, \cdots , p_n$. This means that $q_1$ is a new prime that is not one of the $n$ primes. This contradicts the assumption.

Therefore, prime numbers exist infinitely.

■

See also

• Euler’s Proof