# 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

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