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.

While solving problems in SPOJ, I faced cases where I need to take Modulus of Big numbers like Fibonacci with 10^9 + 7 ( say MOD ). Now, consider the following case :

(Fib(n) + Fib(6*n-1)) / x

As Fib(n) cannot be stored in 64 bit for high n, we are forced to take modulus in every loop of calculating Fibonacci number using Matrix exponentiation. But the division by 'x' later does not give the correct result. That is

(Number/x) % MOD != (Number%MOD)/x generally.

So, in the above cases, is there any way to get correct result? That is Modulus have to be done before division and with that is it possible to get correct result?

share|improve this question
    
What size is $x$ appoximately? Is it guaranteed to be a proper divisor? Should you reply with $\lfloor N/x \rfloor \% MOD$, actually? –  Hagen von Eitzen Sep 5 '12 at 12:09
    
@HagenvonEitzen Yes, x is proper divisor of N. And yeah, required is (N/x)%MOD. –  sabari Sep 5 '12 at 12:38
    
Actually I wanted to calculate the value of the function given in math.stackexchange.com/questions/190443/…. In that result there is division operation. And Modulus operation has to be performed before division in calculation the Lucas number and Fibonacci number. –  sabari Sep 5 '12 at 13:09
add comment

1 Answer 1

up vote 0 down vote accepted

This can be done using the Modular Inverse trick. The concept and the way to find that and also the usage is described with examples here.

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.