# Sum of long geometric progression [closed]

Finding sum of a geometric progression is simple when we just need to report the sum, but when some modulo or multiplicative inverse is asked of that sum the task become tedious for me.

I have a geometric progression: $$\frac{1}{n} + \frac{n-1}{n^2} + \frac{(n-1)^2}{n^3} + \dots$$

Now the sum will be something like

$$1-\left(\frac{n-1}n\right)^r,$$ where $$r$$ is the number of terms.

Now, what if $$r$$ is large, say $$10^4$$?

How do I calculate this?

I used modular exponentiation to calculate the powers of $$n-1$$ and $$n$$ fast, but as we can see these numbers can be quite large.

Let's say $$1-(\frac{n-1}n)^r = P/Q$$.

I tried to output $$PQ^{-1}\bmod1000000007$$ for this, where $$Q^{-1}$$ is the multiplicative inverse of $$Q$$ modulo 1000000007 .

I individually found $$(n-1)^r$$ and $$n^r$$, and then $$P = n^r - (n-1)^r$$, and using same modular exponentiation, it's easy to calculate the numerator. But for the denominator, what I am doing is calculating $$n^r\bmod1000000007$$, and then taking its modular inverse with respect to 1000000007, but I think that's not the correct way to do it.

So how to calculate modular inverse of $$Q$$ when $$Q=n^r \bmod 1000000007$$ and $$r$$ can be large?

I am using Fermat's little theorem, now I just only need advice if it is correct to calculate $$n^r$$ first using modular exponentiation and then taking its modular inverse, or is there any other way?

• I suggest picking up a textbook on elementary number theory. – Yuval Filmus Feb 3 at 15:54
• This question is getting close votes as being pure math. But you're looking for an algorithm, right? Algorithms are on-topic here. Are you always working modulo a prime? – Gilles 'SO- stop being evil' Feb 4 at 8:24
• i solved the problem thank you all! – cooldude Feb 4 at 9:07
• @cooldude What's the solution? Please add an answer so future visitors with similar problems can find it. – Raphael Feb 5 at 7:07