0
$\begingroup$

If $a$ and $p$ are relatively coprime integers, then is there any efficient way of calculating the following: $(\sum_{k=0}^n\frac{1}{a^k}) \% p$ ? I'm interested in the cases when $0 \leq n ≤ 2147483647$ and $2 ≤ p ≤ 2147483647$. Thanks.

1 Answers 1

1

Note that $\sum_{k=0}^n \frac{1}{a^k} = \frac{a^{n+1}-1}{a-1}$. If $n$ is prime then the Euler-Fermat theorem simplifies things a little: $a^{n+1} \equiv a^2 \mod n$. Then your answer becomes $\frac{a^2-1}{a-1} = a+1 \mod n$. But in other situations I'm not sure you get such a nice answer.

  • 0
    thanks..but here p is prime and co-prime to a and not n , still no standard formula?2011-11-13
  • 0
    You're getting an answer mod $n$, but the question asked for the sum mod $p$.2011-11-13
  • 0
    @pranay, there's no formula for $a^{n+1}\pmod p$ better than $a^{n+1}\pmod p$ (unless there is some relation between $p$ and $n$), so do you think there will be a better formula than $(a^{n+1}-1)/(a-1)$ for your question?2011-11-13
  • 0
    no. but besides using exponentiation by squaring, can we use modular exponentiation here ?2011-11-14