Fibonacci sequence modulo m

The Fibonacci sequence is an infinite sequence of integers $f_0,f_1,f_2,\dots$ defined by the initial values $f_0 = f_1 = 1$ and the rule
$$f_{n+1} = f_n + f_{n-1}$$
In other words, to get the next term you take the sum of the two previous terms. For example, it starts off with:
$$1,1,2,3,5,8,13,21,34,55,\dots$$
You can define all sorts of recursive sequences this way and get a whole slew of interesting patterns. The Fibonacci sequence is one of the most well-known, as it is one of the simplest and has connections to the golden ratio:
$$\lim_{n\to \infty} f_n/f_{n-1} = \frac{1 + \sqrt{5}}{2}.$$
In fact, without too great an effort you could derive an exact, closed formula for $f_n$ (i.e. a formula that does not involve recursion, or calculating previous terms to get to the next one) in which appears the golden ratio.

A theme that's been running through my research lately is looking at things modulo $m$ for some integer $m$. Reduction from $\Z$ to $\Z/m$ often happens in mathematics because there is some dictionary that tells you something about an object over $\Z$ if you know something mod $m$. So let's look at the Fibonacci sequence in $\Z/5$. It goes like this:

1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1,…

Very good looking sequence if you ask me. Notice how it starts to repeat, going right back to the beginning. Of course, it has to repeat eventually, because there are only $m^2$ elements in $\Z/m\times\Z/m$. What's a little more interesting is that it goes right back to the beginning $1,1,\dots$, rather than repeating with some new pair that appears a little later.

Why is this? It is because of the recursive definition $f_{n+1} = f_n + f_{n-1}$. We could also write it $f_{n-1} = f_{n+1} – f_n$. Therefore, if two pairs are equal $(f_s,f_{s+1}) = (f_t,f_{t+1})$ with $s \gt t$ then $f_{s-1} = f_{t-1}$. Continuing backwards we see that $f_{s – t} = f_0$ and $f_{s-t+1} = f_1$. This fact was first proved by D.D. Wall of IBM.

This has an amusing consequence for the original Fibonacci sequence: for any integer $n$ there exists a term in the Fibonacci sequence divisible by $n$. That's because the next time $1,1$ comes around, the previous term is zero!

Let's look at the Fibonacci sequence in $\Z/5$ again:

1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1,…

Notice how every element in $\Z/5$ appears in this list. Does that always happen in $\Z/n$? Good question! What about in $\Z/8$? Here is the sequence in $\Z/8$:

1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1,…

Wow, 4 and 6 do not appear! That's pretty weird right? In fact, there can be quite a few values missed. For example, in $\Z/987$ the Fibonacci sequence is

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 0, 610, 610, 233, 843, 89, 932, 34, 966, 13, 979, 5, 984, 2, 986, 1, 0, 1, 1,…

Only 23 residue classes of a possible 987 appear here, and the total length of the repeating segment is 32 (i.e. its period). The period can also be quite long, as it is for $\Z/10$ where it is 60.

Howard Wilcox gave some ways to determine the period of the Fibonacci sequence modulo $m$, but he didn't give an explicit formula. However, a consequence of his research is that aside from $1,1,0,\dots$ in $\Z/2$ which has period three, the period of the Fibonacci sequence in $\Z/m$ for $m\gt 2$ is always even!