How to apply modular arithmatic in expression containing divisions?

Question

How do I find the modulo if the expression contains divisions. Like:

$$\frac{p^a-1}{p-1} \pmod{1000,000,007},$$

where $(p^a-1)$ is divisible by $p-1$ and p is a prime, but a may not be. How do I calculate the modulo ?

Answer 1

1) Compute $X = p^a \pmod {1000000007}$ using Modular Exponentiation.
2) Compute $B = (p - 1)^{-1} \pmod{1000000007}$ using the Extended Euclidean Algorithm.
3) Compute $(X - 1)B \pmod {1000000007}$ using Modular Arithmetic.

---

In your case, $B$ can be calculated easily because $1000000007$ is a prime; more importantly, as long as $p - 1 \ne 1000000007$ then $\operatorname{GCD}(p - 1, 1000000007) = 1$. If it wasn't, this would be a much harder (but not impossible) problem.

To use the Extended Euclidean Algorithm, rewrite the formula for $B$:

$$B \equiv (p - 1)^{-1} \pmod {1000000007} $$ $$(p - 1)B = 1 \pmod {1000000007}$$ $$(p - 1)B - 1000000007n = 1$$

Solve for $n$ and $B$, although you only need $B$.