During AMC testing, the AoPS Wiki is in read-only mode. No edits can be made.

Euclid's proof of the infinitude of primes

This is proved by contradiction. Suppose there is a finite number of primes and let them be $p_1,p_2,p_3,...,p_n$. Let $x=p_1p_2p_3\cdots p_n$. Then we have $x+1=p_1p_2p_3\cdots p_n+1$. When divided by any of the primes $p_1,p_2,p_3,...,p_n$, $x+1$ leaves a remainder of 1 implying that either $x+1$ is prime or that it has some other prime factors not in the set $\{ p_1,p_2,p_3,...,p_n\}$. In any case we have it so that $\{ p_1,p_2,p_3,...,p_n\}$ does not contain all prime numbers. Contradiction!

Invalid username
Login to AoPS