📂Number Theory

Euclid's Proof: There Are Infinitely Many Primes

Theorem¹

There are infinitely many primes.

Explanation

There are several ways to prove that there are infinitely many primes. Among them, we introduce Euclid’s method, which is the simplest. This proof is famous not only for its simplicity but also for its great beauty.

Proof

Assume that there exist only $n$ primes. Let the $n$ primes be $p_1, p_2, \cdots , p_n$ respectively, and consider $p_{n+1}=p_1 p_2 \cdots p_n + 1$.

• If $p_{n+1}$ is prime, then $p_{n+1}$ is a new prime that is not equal to any of the other primes. This contradicts the assumption.
• If $p_{n+1}$ is not prime, then $p_{n+1}$ can be expressed as a product of primes $q_1, q_2, \cdots , q_m$. However, since $q_1$ is also prime, 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, there are infinitely many primes.

■

See Also

• Euler’s Proof