# 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 FreeHortonworks Sandbox for HDP and HDF is your chance to get started on learning, developing, testing and trying out new features. Each download comes preconfigured with interactive tutorials, sample data and developments from the Apache community.

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*.

Hortonworks Community Connection (HCC) is an online collaboration destination for developers, DevOps, customers and partners to get answers to questions, collaborate on technical articles and share code examples from GitHub. Join the discussion.

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 }}