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.
-
$\begingroup$ 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. $\endgroup$– André NicolasAug 21, 2014 at 16:50
-
$\begingroup$ I've always liked this one: cut-the-knot.org/proofs/InjectivePrimes.shtml $\endgroup$– forallepsilonAug 21, 2014 at 16:58
-
1$\begingroup$ @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. $\endgroup$– Andreas BlassAug 21, 2014 at 17:44
-
2$\begingroup$ @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. $\endgroup$– Andreas BlassAug 21, 2014 at 18:17
-
1$\begingroup$ 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. $\endgroup$– Mr. BrooksAug 21, 2014 at 21:25
3 Answers
There are six nice proofs presented in the first chapter of Proofs from THE BOOK, including one similar to yours using Fermat numbers.
The key idea of Euclid's classical proof is that we can construct an infinite sequence of primes from any infinite sequence of coprimes, e.g. give an increasing sequence of naturals $\,f_n > 1\,$ that are pair-coprime, i.e. $\,(f_i,f_j) = 1\,$ for $\,i\ne j,\,$ then choosing $\,p_i\,$ to be a prime factor of $\,f_i\,$ yields an infinite sequence of primes, since the $\,p_i\,$ are distinct: $\,p_i\ne p_j,\,$ being factors of coprimes $\,f_i,\, f_j\,$.
Thus, since the Fermat numbers enjoy such coprimality, they yield an infinite sequence of primes. Ribenboim says the proof using the sequence of Fermat numbers is due to Goldbach (1730), and the idea of using coprimes was used in an exercise by Hurwitz (1891).
You can find these references, and many other proofs that there are infinitely many primes in the first chapter of Ribenboim's The new Book of Prime Number Records.
