Infinitude of Primes - via Fibonacci Numbers

There are infinitely many primes.

Proof

Assume there are only finitely many primes. Let's list them all, omitting \(2\): \(p_1\), \(p_2\), ..., \(p_k\).

Then every element of the following list of the Fibonacci numbers: \(F_{p_1}\), \(F_{p_2}\), ..., \(F_{p_k}\), must be divisible by a different prime because \(\mbox{gcd}(F_{p_i}, F_{p_j})=1\), for \(i\ne j\). The Pigeonhole Principle shows that every \(F_{p_i}\), \(i=1,\ldots ,k\) is divisible by a single prime from the original list. Therefore, \(F_{p_i}\) must be in the form \(2^{a}p^{b}\), with \(p\) an odd prime. But \(F_{19}=37\cdot 113\) is not of this form. We conclude that our assumption leads to a contradiction and is, therefore, wrong.

References

V. H. Moll, Numbers and Functions: From a Classical-Experimental Mathematician's Point of View, AMS, 2012, 113

Infinitude of Primes

71879251