1
$\begingroup$

I have the following expression for $n>3$:

$\frac{5\cdot(n-1)\cdot[8\cdot\operatorname{Luc}(n) + 5\cdot\operatorname{Luc}(n-1)] + [4\cdot\operatorname{Luc}(n-1) - 8\cdot\operatorname{Luc}(n)]}{25}$

where $\operatorname{Luc}(n)$ gives the $n$th term in the Lucas sequence

$ 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, \dots $starting from index $0$.

How do I reduce/rearrange it to remove the $25$ from the denominator? I need this so that I can take the modulus of the entire equation, without first doing any division. (The number in the numerator exceeds $2^{64}$, and I cannot store it in the memory)

  • 0
    @KarolisJuodelė Understood. Got the solution now :) – 2012-09-07

1 Answers 1

1

If you want to get the answer mod n, dividing by 25 is the same as multiply by the inverse of 25 mod n, which you can compute using extended GCD (http://en.wikipedia.org/wiki/Modular_multiplicative_inverse).

This requires that gcd(25,n)=1. If that is not the case, you're in trouble.