2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very cool and sleek answer. I was hoping for a group theoretic answer to this question! $\endgroup$ – Paddling Ghost Jul 13 '15 at 19:11
  • 1
    $\begingroup$ See also oeis.org/A001175 and references there. $\endgroup$ – Robert Israel Jul 13 '15 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.