Fibonacci Numbers and Finite Fields

I found a cool application of finite fields to prove an intriguing result related to Fibonacci numbers last fall. The theorem goes as follows:

If $p\equiv 1,4 \text{ (mod 5)},$ then $F_{p-1}$ is divisible by $p,$
if $p\equiv 2,3 \text{ (mod 5)},$ then $F_{p+1}$ is divisible by $p,$
and $F_5$ is divisible by $5,$

for primes $p>2$ where $F_n$ denotes the $n$ th Fibonacci number.

This statement is both surprising and itself has nothing to do with finite fields, which is why I find it quite interesting. It also happens that using finite fields results in a very elegant proof! Let’s begin.

The first thing to notice is that the perfect squares $\text{(mod 5)}$ are $1,4.$ So, $\Bigl(\frac p5\Bigr)=1$ if and only if $p\equiv 1,4 \text{ (mod 5)}.$ Quadratic Reciprocity tells us that

$\Bigl(\frac p5\Bigr)\Bigl(\frac 5p\Bigr)=(-1)^{\frac{5-1}{2}\cdot\frac{p-1}{2}}=1.$

As a result, $\Bigl(\frac 5p\Bigr)=1$ if and only if $p\equiv 1,4 \text{ (mod 5)}.$

Now, let’s consider the first case, when $p\equiv 1,4 \text{ (mod 5)}.$ Then, $5$ is a perfect square modulo $p.$ That is, there exists some integer $x$ such that $x^2\equiv 5 \text{ (mod p)}.$ In this field, $x$ acts exactly like $\sqrt 5.$ By Binet’s Formula, the $n$ th Fibonacci Number is given by

$F_n=\frac{1}{\sqrt 5}\left[\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right],$

and by Fermat’s Little Theorem, $a^{p-1}=1 \text{ (mod p)},$ so working in our field, we have

$\begin{aligned} F_{p-1}&=\frac{1}{\sqrt 5}\left[\left(\frac{1+\sqrt 5}{2}\right)^{p-1}-\left(\frac{1-\sqrt5}{2}\right)^{p-1}\right]\\ &=\frac{1}{\sqrt 5}\left[1-1\right]\\ &=0. \end{aligned}$

This means that $F_{p-1}$ is a multiple of $p,$ as desired. Note that we can only do this since $\sqrt 5$ “exists.”

Now, let’s move on to the second case, which is a little more interesting. Here, $\sqrt 5$ does not exist modulo $p,$ but we can construct a field with characteristic $p$ such that it does. We introduce a variable $\alpha$ which satisfies the simplification rule $\alpha^2=\alpha+1.$ Then, $\alpha$ acts like a root of the polynomial $f(x)=x^2-x-1.$ Without loss of generality, suppose $\alpha$ is “equivalent” to the root $\frac{1+\sqrt 5}{2}$ So, our field now has $p^2$ . Since the Froebius Automorphism is an automorphism that maps field elements $a$ to $a^p$ , we can say that $f(a)=0$ if and only if $f(a^p)=0,$ and as a result, $\beta=\alpha^p$ is our other root $\frac{1-\sqrt 5}{2}.$ Applying Binet’s Formula again, we have

$\begin{aligned} F_{p+1}&=\frac{1}{\sqrt 5}\left[\alpha^{p+1}-\beta^{p+1}\right]\\ &=\frac{1}{\sqrt 5}\left[\alpha^{p+1}-\left(\alpha^p\right)^{p+1}\right]\\ &=\frac{1}{\sqrt 5}\left[\alpha^{p+1}-\alpha^{p^2-p}\alpha^{p+1}\right]\\ &=\frac{1}{\sqrt 5}\left[\alpha^{p+1}-\alpha^{p+1}\right]\\ &=0. \end{aligned}$

The last case is clear, so we have proven the curious theorem! Although coming up with the proof seems impossible, the main intuition for arriving at the statement lies in embedding the algebraic numbers in Binet’s Formula into fields and playing around with them to see what kind of $p$ th Fibonacci numbers are divisible by their prime $p.$

Further Investigation

Following the same proof methods, as above, I investigated some more possible results. If we replace $F_{p-1}$ and $F_{p+1}$ with $F_p$ in the two first cases of the theorem, we can obtain a similar surprising result. Embedding in the same field of $p$ elements for $p\equiv 1,4 \text{ (mod 5)},$ we get the following:

$\begin{aligned} F_p&=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^p-\left(\frac{1-\sqrt{5}}{2}\right)^p\right] \\ &=\frac{1}{\sqrt{5}}\left[\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}\right] \\ &= \frac{1}{\sqrt{5}}[\sqrt{5}]\\ &=1. \end{aligned}$

This means that when $p\equiv 1,4 \text{ (mod 5)},$ the $p$ th Fibonacci number minus $1$ is a multiple of $p$ . We can do a similar thing for when $p\equiv 2,3 \text{ (mod 5)}.$ Letting $\alpha=\frac{1+\sqrt{5}}{2}$ and $\beta=\frac{1-\sqrt{5}}{2}$ in the field of $p^2$ elements as we did before, we have

$\begin{aligned} F_p&=\frac{1}{\sqrt{5}}(\alpha^p-\beta^p) \\ &=\frac{1}{\sqrt{5}}(\beta^{p^2}-\alpha^{p^2}) \\ &= \frac{1}{\sqrt{5}}(\beta-\alpha) \\ &= \frac{1}{\sqrt{5}}(-\sqrt{5}) \\ &= -1. \end{aligned}$

In this case, when $p\equiv 2,3 \text{ (mod 5)},$ the $p$ th Fibonacci number plus $1$ is a multiple of $p$ . For nice symmetry, we can still say that $F_5$ is a multiple of $5.$

However, like before, given the result

If $p\equiv 1,4 \text{ (mod 5)},$ then $F_{p}-1$ is divisible by $p,$
if $p\equiv 2,3 \text{ (mod 5)},$ then $F_{p}+1$ is divisible by $p,$
and $F_5$ is divisible by $5,$

it is difficult to see how to prove this. However, through almost-magical finite field manipulations, we are able to conclude this. It is strange that we can actually “take” the $-1$ and $+1$ from the subscript of the Fibonacci number to the outside. Despite defying all intuition, this is really awesome, and it neatly exhibits the power of finite fields.

I would love to play around with this more, but I’ll keep it nice and concise for my first post. If anyone reads this, I hope you enjoyed it, and I hope to keep on posting cool little math tidbits in the future!

Source: I first learned about this in Sam Vandervelde’s Finite Fields class, but the result appears in this paper as well: https://math.berkeley.edu/~tb65536/Fibonacci_Exposition.pdf.

Fibonacci Numbers and Finite Fields

Leave a comment Cancel reply