The Fibonacci numbers are defined by the recurrence:

F0=0,F1=1,Fn=Fn1+Fn2forn2. 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:

Fn=ϕnψn5, F_n = \frac{\phi^n - \psi^n}{\sqrt{5}},

where ϕ=1+52\phi = \frac{1 + \sqrt{5}}{2} and ψ=152\psi = \frac{1 - \sqrt{5}}{2} are the roots of the characteristic polynomial x2x1x^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)G(x) such that:

G(x)=F0+F1x+F2x2+F3x3+=n=0Fnxn G(x) = F_0 + F_1x + F_2x^2 + F_3x^3 + \cdots = \sum_{n=0}^{\infty} F_nx^n

In this scenario, GG 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 GG by definition of Fibonacci numbers and then split the sums:

G(x)=n=0Fnxn=0+F1x+n=2Fnxn=F1x+n=2(Fn1+Fn2)xn=F1x+n=2Fn1xn+n=2Fn2xn \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:

n=2Fn1xn=xn=2Fn1xn1=xn=1Fnxn=xG(x)n=2Fn2xn=x2n=2Fn2xn2=x2n=0Fnxn=x2G(x) \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 GG as:

G(x)=F1x+xG(x)+x2G(x) G(x) = F_1x + xG(x) + x^2G(x)

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

G(x)=x1xx2=x(x+ϕ)(x+ψ)=15(11ϕx11ψx) 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 11ϕx\frac{1}{1-\phi x} and 11ψx\frac{1}{1-\psi x}:

G(x)=15(n=0ϕnxnn=0ψnxn) 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)G(x), the coefficient of xnx^n is FnF_n. Hence, we have:

Fn=ϕnψn5 F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}

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

Fn=ϕn5+12 F_n = \Big\lfloor \frac{\phi^n}{\sqrt{5}} + \frac{1}{2} \Big\rceil

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

n=logϕ5(F+12) 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 5n2+45n^2 + 4 or 5n245n^2 - 4 must be a perfect square.


It is known that:

{p=5pFpp±1(mod5)pFp1p±2(mod5)pFp+1 {\displaystyle {\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:

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

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

2n1Fn=2n15(ϕnψn)(1+5)n(15)n25 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 (15)n(1-\sqrt{5})^n and (1+5)n(1+\sqrt{5})^n terms can be written as binomial expansions:

(1+5)n=k=0n(nk)5k(15)n=k=0n(nk)(1)k5k \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+5)n(15)n=2k=0n12(n2k+1)52k+1 (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:

2n1Fn=k0(n2k+1)5k 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>n12k > \frac{n-1}{2}. The second lemma is as follows:

Fp5n(modp)forp=2n+1 F_p \equiv 5^n \pmod{p}\quad \text{for} \quad p = 2n+1

Recall the previous result concerning 2pFp2^p F_p. Fermat’s Little Theorem states, given that pp is prime and aa is an integer not divisible by pp, that:

ap11(modp) a^{p-1} \equiv 1 \pmod{p}

From which we can deduce:

2p2(modp) 2^p \equiv 2 \pmod{p}


2pFp2k0(p2k+1)5k(modp) 2^p F_p \equiv 2 \sum_{k\ge 0} \binom{p}{2k+1} 5^k \pmod{p}

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

2pFp25n(modp) 2^p F_p \equiv 2 \cdot 5^n \pmod{p}

Via Fermat’s Little Theorem, we deduce that:

Fp5n(modp) F_p \equiv 5^n \pmod{p}

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

Fp5(p1)/2(modp) F_{p} \equiv 5^{(p-1)/2} \pmod{p}

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

Fp25p11(modp) F_{p}^2 \equiv 5^{p-1} \equiv 1 \pmod{p}

Per Cassini’s identity - Fn1Fn+1Fn2=(1)nF_{n-1}F_{n+1} - F_n^2 = (-1)^n - we can deduce that:

Fp1Fp+10(modp) F_{p-1}F_{p+1} \equiv 0 \pmod{p}

Hence either pFp+1p \mid F_{p+1} or pFp1p \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(p1)/2(5p)(modp) 5^{(p-1)/2}\equiv\left(\dfrac 5p\right)\pmod p

Hence, arguing that:

Fp(5p)(modp) 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 pp is an odd number, and p±2(mod5)p \equiv \pm 2 \pmod{5}, then pp is prime if both 2p11(modp)2^{p-1}\equiv 1 \pmod{p} and Fp+10(modp)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.

Further reading