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

Question

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

Progress:

$F_{11}=89$ . I believe you should find the period of $F_n \bmod 89$ and use that to solve it. But I'm not not getting anywhere from that.

Thanks!

Answer 1

The correct relationship is $$F_{11k + n} \equiv F_n \cdot F_{10}^k \pmod {F_{11}},$$ and since $1000 = 11(90)+10$, we have $$F_{1000} \equiv F_{10} \cdot F_{10}^{90} = F_{10}^{91} \pmod {F_{11}}.$$ Now we must compute $$55^{91} \pmod {89},$$ and since $89$ is prime, by Fermat's little theorem, we have $$55^{89} \equiv 55 \pmod {89}.$$ Consequently, $$55^{91} = 55^{89} \cdot 55^2 \equiv 55^3 \equiv 34 \pmod {89}.$$

Answer 2

Assuming we're starting with $F_0=0$ and $F_1 = 1$, an easy induction shows that for $n \geq 11$ $$F_n = F_{n-10}\cdot F_{11} + F_{n-11}\cdot F_{10}$$

So $F_n \equiv F_{n-11} \cdot F_{10} \bmod F_{11}$ for $n \geq 11$.

Edit: I made a mistake from here on. See heropup's answer for the rest.