Finding $a \bmod b$ where $a,b$ are large Fibonacci numbers

Question

For moderately large values of $b$ we can use Chinese Remainder Theorem, by factorizing $b$. But for very large values of $b$, (for example $b$ is the 1000th Fibonacci number) factorization will take a lot of time. Is there any other efficient way of finding $a \bmod b$ ( remainder of $b$ divide $a$ ). Does the problem become simple (when compared to the problem for any integer $b$) given the fact that $b$ is a Fibonacci number?

Answer 1

$F_n\equiv 0 \pmod {F_n}$ and $F_{n+1}\equiv F_{n-1}\pmod {F_n}$ means that by induction: $F_{n+k}\equiv F_kF_{n-1}\pmod{F_n}$.

Then, again by an induction argument, we can see that if $m=nq+r$ then $F_{m} \equiv F_r F_{n-1}^q \pmod {F_n}$

This is made easier because $F_{n-1}^2 \equiv (-1)^n \pmod {F_n}$.

Answer 2

Well, Euclid's algorithm is an efficient way to compute $a \pmod{b}$ given any $a$ and $b$ ... much better than factoring.

The fact that the numbers are Fibonacci simplifies the algorithm somewhat, but if $a < b$ then you're just asking for the value of $a$, so you'll always have to compute some potentially big Fibonacci numbers.

Note that $F_{n+1} = F_n + F_{n-1} \equiv F_{n-1} \pmod{F_n}$. Similarly, $F_{n+2} \equiv F_{n-1} \pmod{F_n}$. If you think about the pattern a little bit, you'll realize that modulo $F_{n-1}$ we have that $F_{n+k} = F_k * F_{n-1}$. You can keep recursing more if you like, so you never have to compute any Fibonacci numbers greater than $b$.