3
$\begingroup$

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.

$\endgroup$
10
  • $\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$ Aug 21, 2014 at 16:50
  • $\begingroup$ I've always liked this one: cut-the-knot.org/proofs/InjectivePrimes.shtml $\endgroup$ Aug 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$ Aug 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$ Aug 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. Brooks
    Aug 21, 2014 at 21:25

3 Answers 3

3
$\begingroup$

This page at MIT purports to be an attempt to collect as many proofs as possible. But I suspect it has been left unfinished because it's not very long and there are lots of proofs of this theorem.

This page presents several proofs and could probably be expanded.

$\endgroup$
1
$\begingroup$

There are six nice proofs presented in the first chapter of Proofs from THE BOOK, including one similar to yours using Fermat numbers.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.