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.