Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers

Question

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers.

I have tried using the fact that $F_{n^k} \bmod F_n = 0, k=1,2,3,...$ but that doesn't get me anywhere.

Thanks!

Answer 1

Doing this directly is reasonable by hand. Let's do it now.

One way is to notice that, starting with the matrix $ A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix}$, we get that

$$\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = A^n,$$

where $F_n$ is the $n$th Fibonacci number, and which is very easy to show. Then we can proceed with repeated squaring, performed mod $1001$.

$1001$ is $1111101001$ in binary, so we should compute $9$ powers of $A$, all done mod $1001$. Note that we just square the matrices each time, so it's really not so bad!

$$ \begin{align} A &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \\ A^2 &= \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix} \\ A^4 &= \begin{pmatrix} 5 &3 \\ 3 & 2 \end{pmatrix} \\ A^8 &= \begin{pmatrix} 34 & 21 \\ 21 & 13 \end{pmatrix} \\ A^{16} &= \begin{pmatrix} 596 & 987 \\ 987 & 610 \end{pmatrix} \\ A^{32} &= \begin{pmatrix} 57 & 133 \\ 133 & 925 \end{pmatrix} \\ A^{64} &= \begin{pmatrix} 918 & 476 \\ 476 & 442 \end{pmatrix} \\ A^{128} &= \begin{pmatrix} 705 & 884 \\ 884 & 822 \end{pmatrix} \\ A^{256} &= \begin{pmatrix} 725 & 347 \\ 347 & 378 \end{pmatrix} \\ A^{512} &= \begin{pmatrix} 834 & 338 \\ 338 & 496 \end{pmatrix} \\ \end{align}$$ And to get our answer, we multiply these together, leaving out the $2,4$ and $16$ powers: $$ A^{1001} = \begin{pmatrix} 265 & 650 \\ 650 & 616 \end{pmatrix}$$ and we see that $F_{1000} = 616 \pmod {1001}$. (I could have computed $A^{1000}$ instead, but I gaffed).

---

But there's a better way. Let's use the Chinese Remainder Theorem. As $1001 = 7 \cdot 11 \cdot 13$, we can instead compute it mod $7, 11$ and $13$ and put it together. This is much easier to do by hand.

Using the same method of repeated squaring as above, but where I now omit the matrices (you don't need those again, I bet) and relying instead on the nice fact that multiplication is super easy mod $7$ and $11$, and not so bad mod $13$, we see that $$F_{1000} \begin{cases}\equiv 0 \pmod {7} \\ \equiv 0 \pmod {11} \\ \equiv 5 \pmod {13}\end{cases}$$ What number is $0$ mod $7$ and $11$, and $5$ mod $13$? It's $616$ - hurray!

---

We can do this without matrices, too. The Fibonacci numbers are periodic in any modular arithmetic. So let's see what it will be mod $7, 11, 13$ without resorting to matrices. Mod $7$, it starts like $$0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, \underbrace{0}_{\text{It repeats here, with } F_{16}}, 1, 1, 2, \ldots$$ Mod $11$, we get $$ 0, 1, 1, 2, 3, 5, 8, 2, 10, 1, \underbrace{0}_{F_{10}}, 1, 1, 2, 3, 5, 8, 2, 10, 1,\ldots$$ And mod $13$, we get $$ 0, 1, 1, 2, 3, 5, 8, 0, 8, 8, 3, 11, 1, 12, 0, 12, 12, 11, 10, 8, 5, 0, 5, 5, 10, 2, 12, 1, \underbrace{0}_{F_{28}}, 1, 1, 2,\ldots$$ So we know that $F_{16n} \equiv 0 \mod 7$, $F_{10n} \equiv 0 \mod 11$, and $F_{28n} \equiv 0 \mod 13$.

As $1000$ is divisible by both $10$, we know that $F_{1000} \equiv 0 \mod 11$. Similarly, $F_{1000} \equiv F_8 \equiv 0 \mod 7$, and $F_{1000} \equiv F_{20} \equiv 5 \mod 13$. This leads us to $616$ again!