Cycles in the Fibonacci Sequence mod n with matrices

Question

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.

Answer 1

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.