# Infinite Primes via Fibonacci Numbers

# Infinite Primes via Fibonacci Numbers

### An unusual proof that there are infinite prime numbers.

Join the DZone community and get the full member experience.

Join For FreeHow to Simplify Apache Kafka. Get eBook.

A well-known result about Fibonacci numbers says:

gcd(*F _{m}*,

*F*) =

_{n}*F*

_{gcd(m, n)}

In words, the greatest common divisor of the *m*th and *n*th Fibonacci numbers is the *g*th Fibonacci number where *g* is the greatest common divisor of *m* and *n*. You can find a proof here.

M. Wunderlich used this identity to create a short, clever proof that there are infinitely many primes.

Suppose on the contrary that there are only *k* prime numbers, and consider the set of Fibonacci numbers with prime indices: *F _{p}*

_{1},

*F*

_{p}_{2}, …

*F*. The Fibonacci theorem above tells us that these Fibonacci numbers are pairwise relatively prime: each pair has greatest common divisor

_{pk}*F*

_{1}= 1.

Each of the Fibonacci numbers in our list must have only one prime factor. Why? Because we have assumed there are only *k* prime numbers, and no two of our Fibonacci numbers share a prime factor. But *F*_{19} = 4181 = 37*113. We’ve reached a contradiction, and so there must be infinitely many primes.

**Source**: M. Wunderlich, Another proof of the infinite primes theorem. American Mathematical Monthly, Vol. 72, No. 3 (March 1965), p. 305.

Here are a couple more unusual proofs that there are infinitely many primes. The first uses a product of sines. The second is from Paul Erdős. It also gives a lower bound on π(*N*), the number of primes less than *N*.

12 Best Practices for Modern Data Ingestion. Download White Paper.

Published at DZone with permission of John Cook , DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

## {{ parent.title || parent.header.title}}

## {{ parent.tldr }}

## {{ parent.linkDescription }}

{{ parent.urlSource.name }}