How to calculate (a/b)%c when c is not prime number (a&b are big numbers) ? please provide another algorithm apart from the mentioned below

Question

As by given algorithm (a/b)%c = ((a%c)*((b^-1)%c))%c

but for example (9999/99)%9 = 2 , but by given algorithm it turn out to be 0.

this algorithm is based on the below link. https://www.hackerearth.com/practice/math/number-theory/basic-number-theory-1/tutorial/#c85200

please provide another algorithm apart from mentioned above as it is giving wrong answer for cases as i mentioned above.

Answer 1

Let $d = GCD(a, b), e=\frac{a}{d}, f=\frac{b}{d} $

Now calculate (e/f)%c by a previous algorithm