# 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 < a, n, m \; < 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}&\text{if }a\neq1\pmod m\\n+1&\text{if }a=1\pmod m\end{cases}$$ and use efficient algorithms for multiplicative inversion and exponentiation mod $m$.

• I can't recurrence through N .. It's at least 1,000,000,000 Or do you mean something else .. I've solved it already using this using the following recurrences $S(2k)=S(k)(1+q^k)$ and $S(2k+1)=q S(2k) +1$ where $q = ModularMultiplicativeInverse( a )$ and Got Accepted :) – user1613396 Aug 22 '12 at 3:58
• You do not need to recurse, your formula (without mod) is just a sum of a geometric series and has a solution in a closed form as shown in the answer. Then you have to carry out all operations mod m. – A.Schulz Aug 22 '12 at 6:56