How can I solve for F in the following situation?
$$ F \equiv \frac{n}{d} \pmod{m} \tag 1$$
Denominator d always divides n, but I cannot reduce the fraction directly because n is always huge, and I would need to do modular operations on it first. Denominator d and m are often relatively prime. In those cases I can get to the answer by computing the modular inverse of d modulo m.
Often however denominator d and m are not relatively prime. Let's say $g = gcd(d, m) > 1$. I rewrite the congruence and solve for F:
$$ d \ F \equiv n \pmod{m} \tag 2$$
I can find all g distinct solutions for F in this equation. But how can I determine which is the one that is the answer to the initial equation?
Let $\,g = \gcd(d,m).\,$ Then $\,g\mid d\mid n\,$ so we can cancel $g$ from the top and bottom of $\,n/d\,$ leaving $\,F \equiv (n/g)/(d/g).\,$ If $\,d/g\,$ is coprime to $m$ then then we can compute the fraction by inversion $F\equiv (n/g\bmod m) \,((d/g)^{-1}\bmod m).\,$ Else iterate, again cancelling the gcd of the denominator and modulus. This must eventually terminate with a denominator coprime to the modulus (else the denominators would form an infinite decreasing sequence of positive integers)