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.
finding the sum of series
0
$\begingroup$
sequences-and-series
1 Answers
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.
-
0no. but besides using exponentiation by squaring, can we use modular exponentiation here ? – 2011-11-14