Fibonacci Cyclic Pattern I want to show the Fibonacci numbers are cyclic in mod n. I have tried some small values for n and I can see this is the same. In terms of a proof, I'm thinking of using the pigeonhole principle of pair of adjacent Fibonacci numbers but I think I'm going in the wrong direction.....any help will be appreciated.
Many Thanks.
 A: Denoting $f_k:=F_k\bmod n$, you obviously have
$$f_{k+2}=(f_{k+1}+f_k)\bmod n=\phi(f_{k+1},f_k).$$
As the $f_k$ take at most $n$ different values, after at most $n^2$ steps you have exhausted all possible pairs and the iterations must cycle.
For example, with $n=3$ the sequence is
$$0,1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1\cdots$$
The function $\phi$ corresponds to the finite table
$$\begin{array}{ccc}
&\textbf0 & \textbf1 & \textbf2 \\
\textbf0&0 & 1 & 2 \\
\textbf1&1 & 2 & 0 \\
\textbf2&2 & 0 & 1 \end{array}$$
where the entry $\phi(0,0)$ is never used.

It can be shown that in fact the length of the period never exceeds $6n$.
A: Consider the pairs $u_k=(F_{k+1} \bmod n, F_{k} \bmod n) \in M \times M$, where $M = \{ 0, 1, \dots, m-1 \}$.
Since $M \times M$ is finite (it has $m^2$ elements), it is clear that the sequence $u_k$ is preperiodic, that is, $u_{r+p}=u_r$ for some $r \ge 0$ and $p>0$. In other words, $u_k$ repeats with period $p$ after $k=r$.
To prove that $u_k$ is periodic you'll need to argue that $r=0$ works.
