Solving $\text{key}=(\sum_{K=0}^n\frac{1}{a^K})\bmod m$ with High limits I was solving this equation:
$$\text{key}=\left(\sum_{K=0}^n\frac{1}{a^K}\right)\bmod{m}.$$
Given
$$ 1,000,000,000 &lt; a, n, m \; &lt; 5,000,000,000, $$
$$ a, m \text{ are coprime}. $$
I solved it by brute force, but it won't work in the given constrains so I need a faster algorithm or is there is something I can notice to make the formula easier to solve ?
Solve a linear homogeneous recurrence to obtain the identity $$\sum_{K=0}^n\frac1{a^K}=\begin{cases}\frac{1-1/a^{n+1}}{1-1/a}&amp;\text{if }a\neq1\pmod m\\n+1&amp;\text{if }a=1\pmod m\end{cases}$$ and use efficient algorithms for multiplicative inversion and exponentiation mod $m$.