There is another quick trick to find mod inverse when mod is prime.
Basically, 1/a mod m = a^(m-2) mod m if m is prime (This is derived from Fermat's theorem)
It doesn't work when m is non-prime. What can we do then?
Then, we can derive from Euler's theorem that 1/a mod m = a^(phi(m) - 1) mod m where phi(m) = number of coprimes of m which are smaller than m.