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)

  • 1
    If $25$ is coprime to $p$ (as in $\pmod{p}$), then $a/b \pmod{p} \equiv (a \pmod{p})/(b \pmod{p}) \pmod{p}$. Does that help?2012-09-07
  • 0
    Elements of the sequence $f_n = \frac{n-1}{5} \left( 8 L_{n} + 5 L_{n-1}\right) + \frac{4}{25} \left( 2 L_n - L_{n-1} \right)$ are not integral. For instance, $f_2 = \frac{33}{5}$. Are you expecting to end-up with $5$ in the denominator?2012-09-07
  • 0
    For $n=9$, the result is $\dfrac{6828}{5}$. Is there possibly a typo?2012-09-07
  • 0
    @KarolisJuodelė : the value of p = (10^9 + 7). Which is Coprime to 25. But How will this help ? if a = 150 , b = 25 and p =27 (p is coprime to b) , but (a/b)%p != ((a%p)/(b%p))%p . Or am I understanding the concept wrong ?2012-09-07
  • 0
    @Sasha : The values are only for n>32012-09-07
  • 0
    @DrKW : Sorry there must be a typo. This expression is a reduced form of another expression. Must have made a typo in that. The value for n=9 is 1332.2012-09-07
  • 0
    @Kyuubi, the thing is that division in $\mathbb{N}$ is not the same as division $\pmod{p}$. The latter is $a/b = b^{-1}a$ where $b^{-1}b \equiv 1 \pmod{p}$.2012-09-07
  • 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.