0
$\begingroup$

I have numbers $a$, $b$ and $m$, and I need to get the result of $\ \dfrac{a}{b} \mod m$.

The catch is that while $m \leq 10^9$, $a$ and $b$ can get extremely large ($2^{100,000}$), so I'm keeping them as a multiset of their prime factors.

I read about modular multiplicative inverse but I haven't found a way to use it in this problem and would appreciate any help.

Also, note that $m$ is not necessarily prime;

$\endgroup$
  • 1
    $\begingroup$ Modular multiplicative inverse is exactly what you need and solves exactly your problem. What have you tried? Where did you get stuck? Have you tried finding the inverse of $b$ modulo $m$? Do you know that you can multiply modulo $m$ very efficiently? $\endgroup$ – D.W. Nov 12 '14 at 21:36
  • $\begingroup$ The bit I was missing was that I need to multiply modular inverses of each $b_i$ as @Yuval stated below. $\endgroup$ – Andrej Karadzic Nov 12 '14 at 22:37
2
$\begingroup$

If $a = \prod_i a_i$ and $b = \prod_j b_j$ then $$\frac{a}{b} \pmod{m} = \prod_i a_i \pmod{m} \times \prod_j b_i^{-1} \pmod{m},$$ where the products on the right are performed modulo $m$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.