Fibonacci Sequence in $\mathbb Z_n$.

Consider a Fibonacci sequence, except in $\mathbb Z_n$ instead of $\mathbb Z$:

$$F(1) = F(2) = 1$$ $$F(n+2) = F(n+1) + F(n)$$

It is easy to see that each of these sequences must cycle through some sequence and repeat. Consider, for example, the sequence in $\mathbb Z_4$:

$$1,1,2,3,1,0,1,1,2,3,1,0,\dots$$

Is there a nice way to describe the length of the sequence that results before repeating? Clearly, it must be less than $n^2$, since that would cycle through all possible combinations of $a,b$ with $a,b \in \mathbb Z_n$, and once you repeat two combinations, you have a cycle.

\begin{align*} \mathbb Z_2: 1,1,0,\dots & 3 \\ \mathbb Z_3: 1,1,2,0,2,2,1,0,\dots & 8 \\ \mathbb Z_4: 1,1,2,3,1,0,\dots & 6 \\ \mathbb Z_5: 1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,\dots & 20 \end{align*}

Examining the sequences above, it seems "obvious" that there's some pattern (just look at how $0$ occurs every $5$th number). Is there a "nice" way to describe these sequences (such as a way to calculate the $k^{th}$ term in a sequence), and, in particular, a rule for the lengths of the cycles?

Solution 1:

I found a way to do this with prime $n.$ Not sure how well it extends to prime powers.

We want to know what happens to the pair of consecutive entries $(x,y),$ shifting over one to get $(y,x+y).$ So we define the matrix $$ A \; = \; \left( \begin{array}{rr} 0 & 1 \\ 1 & 1 \end{array} \right) , $$ and note $$ \left( \begin{array}{rr} 0 & 1 \\ 1 & 1 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) \; = \; \left( \begin{array}{c} y \\ x+ y \end{array} \right) $$

We find $A^2 = A + I,$ as well as $A^{-1} = A - I.$ As a result, the set of sums of powers of $A$ make a commutative ring; we calculate $$ A^3 = 2A + I, $$ $$ A^4 = 3A + 2I, $$ $$ A^5 = 5A + 3I, $$ $$ A^6 = 8A + 5I, $$ $$ A^7 = 13A + 8I, $$ $$ A^8 = 21A + 13I, $$ and so on. We do not know for sure that we have a repetition until we have repeated the pair $(x,y).$ Next, what if we regard the coefficients in this ring as elements of the field $\mathbf Z / p \mathbf Z ?$

We would like to know the smallest $m$ such that $$ A^m \equiv I \pmod p. $$ There are two parts to this. We illustrate first. $$ A^3 \equiv I \pmod 2. $$ $$ A^4 \equiv 2I \pmod 3, 2^2 \equiv 1 \pmod 3, A^8 \equiv I \pmod 3. $$ $$ A^5 \equiv 3I \pmod 5, 3^4 \equiv 1 \pmod 5, A^{20} \equiv I \pmod 5. $$ $$ A^8 \equiv 6I \pmod 7, 6^2 \equiv 1 \pmod 7, A^{16} \equiv I \pmod 7. $$ For each prime, the second exponent is a factor of $p-1,$ as $$ \lambda^{p-1} \equiv 1 \pmod p. $$

I forgot one item earlier. If $p \equiv 2,3 \pmod 5,$ then there are no solutions to $x^2 - x - 1 \pmod p,$ the thing is irreducible, and our ring of matrices is a field with $p^2$ elements. The set of nonzero elements is a multiplicative group with $p^2 - 1$ elements. It follows that, with our $A^m \equiv I \pmod p,$ that $m | (p^2 - 1).$

For $p = 5$ or $p \equiv 1,4 \pmod 5,$ the ring has zero divisors, given explicitly by the factors of $x^2 - x - 1 \pmod p$ and scalar multiples of those. Annoying. On the other hand, for $p \equiv 1,4 \pmod 5$ it appears $A^{p-1} \equiv I \pmod p,$ true for $p=11,19,29,31,41,$ and perhaps provable.

From the link given in comments above about Pisano periods, I finally understand how to do $p \equiv 1,4 \pmod 5.$ Let $\phi$ be either of the two distinct roots of $\phi^2 - \phi - 1 \equiv 0 \pmod p. $ Then, with the numbering $F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5,$ we find $$ F_n = \frac{\phi^n - (1-\phi)^n}{2 \phi - 1}. $$ Using $a^{p-1} \equiv 1 \pmod p$ and $\phi^2 \equiv \phi + 1 \pmod p$ and $\frac{1}{\phi} \equiv \phi - 1 \pmod p,$ we find both $$ F_{p-1} \equiv 0 \pmod p, \; \; \; F_{p-2} \equiv 1 \pmod p. $$ From our earlier discussion of the matrix $A,$ we see that $$ A^n = F_n A + F_{n-1} I, $$ pointed out below by awllower. So $$ A^{p-1} = F_{p-1} A + F_{p-2} I \equiv I \pmod p. $$ As a result, any such sequence, Fibonacci or Lucas or what have you, repeats with period $p-1$ or some divisor thereof.