# Congruence equation with rational expression

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)
• Sometimes $d = g = gcd(d, m)$. Then this doesn't get me anywhere. Am I missing something?
• Even though $d = (d, m)$ happens rarely, when $d \ne (d, m)$ and I can make denominator coprime to m, I still have $n / g$ with denominator I can't invert, and a fraction which I can't reduce, as I said, because $n$ is always huge and I can only compute it modulo $m$.