Euclid’s proof of the infinitude of primes

If there were only a finite amount of primes then there would be some largest prime p. However p!+1 is not divisible by any number 1<np, since p! is, so p!+1 cannot be factored by the primes we already know, but every integer greater than one is divisible by at least one prime, so there must be some prime greater than p by which p!+1 is divisible.

Actually Euclid did not use p! for his proof but stated that if there were a finite list p1,,pn of primes, then the number p1pn+1 is not divisible by any of these primes and thus either prime and not in the list or divisible by a prime not in the list.

Title Euclid’s proof of the infinitude of primes
Canonical name EuclidsProofOfTheInfinitudeOfPrimes
Date of creation 2013-03-22 12:44:07
Last modified on 2013-03-22 12:44:07
Owner mathwizard (128)
Last modified by mathwizard (128)
Numerical id 9
Author mathwizard (128)
Entry type Proof
Classification msc 11A41