1
$\begingroup$

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?

$\endgroup$

closed as off-topic by David Richerby, Discrete lizard, Evil, Yuval Filmus, Luke Mathieson Feb 12 at 23:51

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about computer science, within the scope defined in the help center." – David Richerby, Discrete lizard, Evil, Yuval Filmus, Luke Mathieson
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I suggest picking up a textbook on elementary number theory. $\endgroup$ – Yuval Filmus Feb 3 at 15:54
  • 1
    $\begingroup$ 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? $\endgroup$ – Gilles Feb 4 at 8:24
  • $\begingroup$ i solved the problem thank you all! $\endgroup$ – cooldude Feb 4 at 9:07
  • 1
    $\begingroup$ @cooldude What's the solution? Please add an answer so future visitors with similar problems can find it. $\endgroup$ – Raphael Feb 5 at 7:07