Dividing large numbers modulo m
-
01-11-2019 - |
Question
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;
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange