# Infinitude of prime numbers

Everyone knows that there is an infinitude of primes. I know the Euclide, the Euler and the Erdos proofs. But are they the only known proofs ? I will try, here, to present a fourth one : Let the Fermat numbers $F_n=2^{2^n}+1$. They are not all primes, $F_5$ for example is not, Euler has proved it ! There are two possibilities, of course : if there is an infinitude of prime Fermat numbers, the primes are infinite. If there is an infinitude of compound Fermat numbers, the Goldbach theorem states that $\gcd(F_n,F_m)=1$ if $n\neq m$. So $F_n=p_1^{n_1}\cdots p_i^{n_i}$ and $F_m=q_1^{m_1}\cdots q_j^{m_j}$ and $p_k\neq{q_j},\forall{j,k}$. Thus $p_1=F_n^{1/n_1}p_2^{-n_2/n_1}\cdots p_i^{-n_i/n_1}$ are infinite and there is always an infinitude of primes! Do you know another proof mentioned in the literature, please? Thank you.

• We don't need to break into cases. For each Fermat number $F_m$, let $p_m$ be its smallest prime factor. The $p_m$ are all distinct. – André Nicolas Aug 21 '14 at 16:50
• I've always liked this one: cut-the-knot.org/proofs/InjectivePrimes.shtml – forallepsilon Aug 21 '14 at 16:58
• @Hurkyl The first dictionary I checked gives, as one meaning of "infinity", "an infinite or very great number or amount". So I think "an infinity of primes" is quite correct. – Andreas Blass Aug 21 '14 at 17:44
• @Hurkyl Googling "an infinity of" I found lots of usesof this construction. Then, restricting the search by adding "math", I still found lots of uses and, on the few Google pages that I actually looked into, no claims that it's a misuse except for your comment here. – Andreas Blass Aug 21 '14 at 18:17
• My hunch is that any rigorous book about prime numbers probably has at least one other proof besides the classic one. Somewhere I read a proof that I thought was inelegant because it requires proving the fundamental theorem of arithmetic first, and I don't know, the infiniteness of primes seems to me like a more elementary thing than unique factorization. – Mr. Brooks Aug 21 '14 at 21:25

The key idea is: any infinite sequence $\,f_n > 1 \,$ of coprimes yields an infinite sequence of distinct primes $\, p_n$ obtained by choosing $\,p_n$ to be any prime factor of $\,f_n,\,$ e.g. the least factor $> 1.$