Euclid's Proof
back

Here is a very terse account of Euclid's proof
that there exist infinitely many primes.
Consider the numbers
(1)=1+1
(2)=2 times 1 + 1
(3)=3 times 2 times 1 + 1
(4)=4 times 3 times 2 times 1 + 1.
etc.
The number (n) is not divisible by any number less than n,
because such a division leaves a remainder of 1. On the
other hand, (n) must factor into primes. Therefore, there
exists a prime number larger than n. Since n is arbitrary
there are infinitely many primes.