<s>[INST] 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?
 [/INST] 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.
</s>