World's most popular travel blog for travel bloggers.

# Dividing large numbers modulo m

, ,
Problem Detail:

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;

###### Answered By : Yuval Filmus

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