ProofThatThereAreInfinitelyManyPrimes 2002-06-04 15:02:01 2008-07-14 13:19:29 Proof prime 0 % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here 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<n\leq p$, 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,\ldots,p_n$ of primes, then the number $p_1\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.