iczelia :: The link between Fibonacci numbers and primes

Preliminaries ⎇

The Fibonacci numbers are defined by the recurrence:

$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \quad \text{for} \quad n \geq 2.$

A closed form of this formula is given by Binet's formula:

$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}},$

where $\phi = \frac{1 + \sqrt{5}}{2}$ and $\psi = \frac{1 - \sqrt{5}}{2}$ are the roots of the characteristic polynomial $x^2 - x - 1$ . There are many alternative proofs for this established fact, but the author's favourite concerns generating functions. Suppose that we want to find $G(x)$ such that:

$G(x) = F_0 + F_1x + F_2x^2 + F_3x^3 + \cdots = \sum_{n=0}^{\infty} F_nx^n$

In this scenario, $G$ is a generating function for the Fibonacci numbers - in other words, it is a formal power series whose coefficients are the Fibonacci numbers. We rewrite $G$ by definition of Fibonacci numbers and then split the sums:

$\begin{aligned} G(x) &= \sum_{n=0}^{\infty} F_nx^n = 0 + F_1x + \sum_{n=2}^{\infty} F_nx^n \\\\ &= F_1x + \sum_{n=2}^{\infty} (F_{n-1} + F_{n-2})x^n \\\\ &= F_1x + \sum_{n=2}^{\infty} F_{n-1}x^n + \sum_{n=2}^{\infty} F_{n-2}x^n \end{aligned}$

Now, focusing on the sums we notice that:

$\begin{aligned} \sum_{n=2}^{\infty} F_{n-1}x^n &= x\sum_{n=2}^{\infty} F_{n-1}x^{n-1} = x\sum_{n=1}^{\infty} F_{n}x^{n} = xG(x) \\\\ \sum_{n=2}^{\infty} F_{n-2}x^n &= x^2\sum_{n=2}^{\infty} F_{n-2}x^{n-2} = x^2\sum_{n=0}^{\infty} F_{n}x^{n} = x^2G(x) \end{aligned}$

Hence we can rewrite $G$ as:

$G(x) = F_1x + xG(x) + x^2G(x)$

From which we can isolate $G$ and substitute $F_1 = 1$ . Then, we factor the denominator.

$G(x) = \frac{x}{1 - x - x^2} = \frac{x}{-(x+\phi)(x+\psi)} = \frac{1}{\sqrt 5} \left( \frac{1}{1-\phi x} - \frac{1}{1 - \psi x} \right)$

We can expand the geometric series for $\frac{1}{1-\phi x}$ and $\frac{1}{1-\psi x}$ :

$G(x) = \frac{1}{\sqrt 5} \left( \sum_{n=0}^{\infty} \phi^n x^n - \sum_{n=0}^{\infty} \psi^n x^n \right)$

By definition of the generating function $G(x)$ , the coefficient of $x^n$ is $F_n$ . Hence, we have:

$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$

Which concludes the proof. A few other facts follow from Binet's formula, for example:

$F_n = \Big\lfloor \frac{\phi^n}{\sqrt{5}} + \frac{1}{2} \Big\rceil$

Where $\lfloor x \rceil$ denotes the nearest integer to $x$ . This is a useful fact for approximating Fibonacci numbers, and it can be proven by noticing that $|\frac{\psi^n}{\sqrt{5}}| < \frac{1}{2}$ for all $n \geq 0$ . A formula that allows us to determine the largest Fibonacci number less than a given number $x$ is:

$n = \Big\lfloor \log_{\phi} \sqrt{5} \left(F + \frac{1}{2}\right) \Big\rceil$

Another interesting corollary of Binet's formula states the sufficient and necessary condition for a natural number to be a Fibonacci number: either of $5n^2 + 4$ or $5n^2 - 4$ must be a perfect square.

Divisibility ⎇

It is known that:

${\begin{cases}p=5&\Rightarrow p\mid F_{p}\\\\ p\equiv \pm 1{\pmod {5}}&\Rightarrow p\mid F_{p-1}\\\\ p\equiv \pm 2{\pmod {5}}&\Rightarrow p\mid F_{p+1}\end{cases}}$

Or, written more succinctly as:

$p\mid F_{p-\left({\frac {5}{p}}\right)}$

Where $\left({\frac {5}{p}}\right)$ is the Legendre symbol. We prove this fact by introducing two auxiliary lemmas, the first of which gives $2^{n-1} F_n$ as a sum of binomial coefficients, a result initially stated by Catalan:

$2^{n-1} F_n = \frac{2^{n-1}}{\sqrt{5}} \left( \phi^n - \psi^n \right) \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2\sqrt{5}}$

Notice how the $(1-\sqrt{5})^n$ and $(1+\sqrt{5})^n$ terms can be written as binomial expansions:

$\begin{aligned} (1+\sqrt{5})^n &= \sum_{k=0}^{n} \binom{n}{k} \sqrt{5}^k \\\\ (1-\sqrt{5})^n &= \sum_{k=0}^{n} \binom{n}{k} (-1)^k \sqrt{5}^k \end{aligned}$

Further, if we subtract those expansions, the even terms cancel out, while the odd terms double:

$(1+\sqrt{5})^n - (1-\sqrt{5})^n = 2\sum_{k=0}^{\lfloor \frac{n-1}{2} \rfloor} \binom{n}{2k+1} \sqrt{5}^{2k+1}$

Substituting into the original expression and simplifying, we obtain:

$2^{n-1} F_n = \sum_{k\ge 0} \binom{n}{2k+1} 5^k$

The limits of summation are irrelevant, as the binomial coefficients vanish for $k > \frac{n-1}{2}$ . The second lemma is as follows:

$F_p \equiv 5^n \pmod{p}\quad \text{for} \quad p = 2n+1$

Recall the previous result concerning $2^p F_p$ . Fermat's Little Theorem states, given that $p$ is prime and $a$ is an integer not divisible by $p$ , that:

$a^{p-1} \equiv 1 \pmod{p}$

From which we can deduce:

$2^p \equiv 2 \pmod{p}$

Hence:

$2^p F_p \equiv 2 \sum_{k\ge 0} \binom{p}{2k+1} 5^k \pmod{p}$

However, all $\binom{p}{2k+1}$ are divisible by $p$ , except $\binom{p}{p} = 1$ . Therefore:

$2^p F_p \equiv 2 \cdot 5^n \pmod{p}$

Via Fermat's Little Theorem, we deduce that:

$F_p \equiv 5^n \pmod{p}$

Coming back to the original statement, we begin by proving the edge cases: if $p = 2$ , then $2 \mid F_3$ . On the other hand, if $p = 3$ , then $3 \mid F_4$ . The statement $5 \mid F_5$ is trivial, as $F_5 = 5$ . We apply the second lemma to $F_p$ :

$F_{p} \equiv 5^{(p-1)/2} \pmod{p}$

Squaring both sides and applying Fermat's little theorem states that:

$F_{p}^2 \equiv 5^{p-1} \equiv 1 \pmod{p}$

Per Cassini's identity - $F_{n-1}F_{n+1} - F_n^2 = (-1)^n$ - we can deduce that:

$F_{p-1}F_{p+1} \equiv 0 \pmod{p}$

Hence either $p \mid F_{p+1}$ or $p \mid F_{p-1}$ , but not both by definition of Fibonacci numbers. On the other hand, we the following holds due to quadratic reciprocity:

$5^{(p-1)/2}\equiv\left(\dfrac 5p\right)\pmod p$

Hence, arguing that:

$F_p \equiv \left(\dfrac 5p\right) \pmod{p}$

And the proof of the original statement follows.

Primality tests ⎇

A conjecture due to John Selfridge is that if $p$ is an odd number, and $p \equiv \pm 2 \pmod{5}$ , then $p$ is prime if both $2^{p-1}\equiv 1 \pmod{p}$ and $F_{p+1}\equiv 0\pmod{p}$ hold. A variety of primality tests have been conjectured based on this statement, like the PSW test or the Baillie-PSW test.

The link between Fibonacci numbers and primes

Preliminaries ⎇

Divisibility ⎇

Primality tests ⎇

Further reading ⎇