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
    no. but besides using exponentiation by squaring, can we use modular exponentiation here ?2011-11-14