# finding the sum of series

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.

-

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.
You're getting an answer mod $n$, but the question asked for the sum mod $p$. –  Gerry Myerson Nov 13 '11 at 23:27
@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? –  Gerry Myerson Nov 13 '11 at 23:31