1

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?

BoLe
  • 369

1 Answers1

1

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)

Bill Dubuque
  • 272,048
  • Sometimes $d = g = gcd(d, m)$. Then this doesn't get me anywhere. Am I missing something? – BoLe Aug 13 '17 at 19:24
  • 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$. – BoLe Aug 13 '17 at 19:51
  • I don't think you can do any better in general. What is your context? – Bill Dubuque Aug 13 '17 at 20:04
  • I shouldn't say. The problem is part of a site with a code I try to follow. But will you be willing by any chance to review my short work in an e-mail and give me a tiny push in the right direction should you discern it? – BoLe Aug 14 '17 at 08:36