Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

$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}$.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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