# 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 $$, 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 ${p}_{1},\mathrm{\dots},{p}_{n}$ of primes, then the number ${p}_{1}\mathrm{\cdots}{p}_{n}+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 |