Preliminaries⌗

The Fibonacci numbers are defined by the recurrence:

F0=0,F1=1,Fn=Fn−1+Fn−2forn≥2. 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 ψ=1−52\psi = \frac{1 - \sqrt{5}}{2} are the roots of the characteristic polynomial x2−x−1x^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=0∞Fnxn 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=0∞Fnxn=0+F1x+∑n=2∞Fnxn=F1x+∑n=2∞(Fn−1+Fn−2)xn=F1x+∑n=2∞Fn−1xn+∑n=2∞Fn−2xn \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=2∞Fn−1xn=x∑n=2∞Fn−1xn−1=x∑n=1∞Fnxn=xG(x)∑n=2∞Fn−2xn=x2∑n=2∞Fn−2xn−2=x2∑n=0∞Fnxn=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)=x1−x−x2=x−(x+ϕ)(x+ψ)=15(11−ϕx−11−ψ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∞ϕnxn−∑n=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 n≥0n \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 5n2−45n^2 - 4 must be a perfect square.

Divisibility⌗

It is known that:

{p=5⇒p∣Fpp≡±1(mod5)⇒p∣Fp−1p≡±2(mod5)⇒p∣Fp+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:

p∣Fp−(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 2n−1Fn2^{n-1} F_n as a sum of binomial coefficients, a result initially stated by Catalan:

2n−1Fn=2n−15(ϕn−ψn)(1+5)n−(1−5)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 (1−5)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(1−5)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−(1−5)n=2∑k=0⌊n−12⌋(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:

2n−1Fn=∑k≥0(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>n−12k > \frac{n-1}{2}. The second lemma is as follows:

Fp≡5n(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:

ap−1≡1(modp) a^{p-1} \equiv 1 \pmod{p}

From which we can deduce:

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

Hence:

2pFp≡2∑k≥0(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:

2pFp≡2⋅5n(modp) 2^p F_p \equiv 2 \cdot 5^n \pmod{p}

Via Fermat’s Little Theorem, we deduce that:

Fp≡5n(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 2∣F32 \mid F_3. On the other hand, if p=3p = 3, then 3∣F43 \mid F_4. The statement 5∣F55 \mid F_5 is trivial, as F5=5F_5 = 5. We apply the second lemma to FpF_p:

Fp≡5(p−1)/2(modp) F_{p} \equiv 5^{(p-1)/2} \pmod{p}

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

Fp2≡5p−1≡1(modp) F_{p}^2 \equiv 5^{p-1} \equiv 1 \pmod{p}

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

Fp−1Fp+1≡0(modp) F_{p-1}F_{p+1} \equiv 0 \pmod{p}

Hence either p∣Fp+1p \mid F_{p+1} or p∣Fp−1p \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≡(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 2p−1≡1(modp)2^{p-1}\equiv 1 \pmod{p} and Fp+1≡0(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⌗