Cycles in the Fibonacci Sequence mod n with matrices I was just looking at this question about Fibonacci sequence cycles modulo 5, and I happened to see a very nice solution that involved using matrices.  Using the matrix representation of the Fibonacci sequence, one can reduce the problem of finding cycles modulo $n$ to a certain problem concerning matrices.  Thus, my question is such:  
Given an integer $n$, does there exist an integer $x$ such that \begin{align}
\begin{bmatrix}
1 & 1 \\
1 & 0 
\end{bmatrix}^x \equiv
\begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix} \pmod n
\end{align}
Surely there are some values of $n$ that have no associated $x$ satisfying the above equation.  In general, what values of $n$ have an associated $x$ that satisfies the above equation.  If you haven't looked at the linked answer, my question relates to the Fibonacci sequence in the following way:  If there exists an integer $n$ and an integer $x$ that satisfy the equation above, then the fibonacci sequence $ \pmod n$ repeats every $x$ terms.  That is,  $F_{i}\equiv F_{i+x}\pmod n$
To reiterate, can we characterize those integers $n$ for which there exists an associated integer $x$ that satisfies the matrix equation above?
For $n=5$ we have the $x$ value of 20.
For $n=6$ we have the $x$ value of 24.
I am very interested to know if there are infinitely many solutions like this, or perhaps there is some largest $n$?  (I doubt the latter)  I am also interested to know what sorts of techniques can be used to solve the above matrix equation.  As always, please leave a comment to let me know if I messed something up or was unclear anywhere.
 A: Yes. To any integer $n$ there is such an exponent $x$. The reason is the following. The matrix $\pmatrix{1&1\cr1&0\cr}$ has determinant $-1$. This is coprime to $n$ irrespective of the value of $n$. Therefore the matrix belongs to the finite group of invertible $2\times2$ matrices with entries in the ring $\Bbb{Z}_n$. Lagrange's theorem (or elementary group theory) then tells you that such an $x$ exists.

But we can see the periodicity of the modular Fibonacci sequence also without group theory. Consider the pairs of remainders of two consecutive Fibonacci numbers $(\overline{F_k},\overline{F_{k+1}})$ modulo $n$. There are only finitely many possible pairs, $n^2$ to be precise. Therefore by the pigeonhole principle there exist integers $k,\ell, 0\le k<\ell\le n^2$, such that the corresponding pairs coincide: $F_k\equiv F_\ell\pmod n$ AND $F_{k+1}\equiv F_{\ell+1}\pmod n$. 
Because the Fibonacci sequence has recursion depth two, a pair of consecutive values determines the future of the sequence completely. This means that once a pair of two consecutive remainders repeats, the sequence must be periodic from that point on. Because the pair $(F_k,F_{k+1})$ also determines the past (the recursion works also backwards), it must have been periodic from the beginning.
