# Dividing large numbers modulo m

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;

• 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? – D.W. Nov 12 '14 at 21:36
• The bit I was missing was that I need to multiply modular inverses of each $b_i$ as @Yuval stated below. – Andrej Karadzic Nov 12 '14 at 22:37

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