# 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?

#### Solutions Collecting From Web of "Fibonacci Sequence in $\mathbb Z_n$."

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.