0

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 ?

Tamim Addari
  • 895
  • Hint: for any prime $;p;,;;a^p=a\pmod p;$ ... – DonAntonio Apr 14 '14 at 15:10
  • But here p may not be a prime. But a is a prime . – Tamim Addari Apr 14 '14 at 15:13
  • You do modular division. –  Apr 14 '14 at 15:15
  • 1
    If $p$ is not a prime necessarily, it would help to not write it as $p$. – MT_ Apr 14 '14 at 15:20
  • Edited, What is modular division? – Tamim Addari Apr 14 '14 at 15:24
  • 1
    The primeness of $a$ and $p$ are irrelevant actually; what really matters is whether $\gcd(p-1, 1000000007) = 1$ or not. –  Apr 14 '14 at 15:25
  • @Hurkyl,what should I do if gcd(p-1,10000000007) is not 1 ? I am really weak in modular arithmatic. – Tamim Addari Apr 14 '14 at 15:26
  • Suppose you want to find $x / 3 \pmod {11}$. First you find $b$ such that $3 \cdot b = 1 \pmod {11}$, in this case $b = 4$. Then you have $x / 3 = x \cdot 4 \pmod {11}$, that's how you do modular division. You basically find $a^{-1} = b \pmod p$ and convert $x / a$ to $x \cdot b$, but the inverse doesn't always exist. – DanielV Apr 14 '14 at 15:28
  • If you look at the "related" section on the right, there are a few questions about modular inverses and modular division you can look at. –  Apr 14 '14 at 16:28
  • @TamimAdDari Are you trying to compute a value or are you trying to analyze an expression? – DanielV Apr 14 '14 at 16:35
  • I am trying to compute the value in a computer program. But as a and p can be very large that won't fit in the memory so I have to follow some technique. – Tamim Addari Apr 14 '14 at 17:15

1 Answers1

2

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$.

DanielV
  • 23,556