# Doing modular division when denominator and modulus not coprime

So normally if you calculate $n/d \mod m$, you make sure $d$ and $m$ are coprime and then do $n[d]^{-1}\mod m$ , all $\mod m$. But what if $d$ and $m$ are not coprime? What do you do?

• You don't do anything because the division is not possible mod $m$; much like the answer to "if you calculate $n/d$ when $d\ne0$, you're fine - what do you do if $d=0$?" However if you can divide $n/d$ prior to reduction mod $m$ and get a rational whose denominator shares no nontrivial factor with $m$, then you're free to do so. Is there context that precedes this question that you want help with? For instance, $ax\equiv b\bmod m$ when $a,b,m$ share a common factor $c$ can be reduced to $(a/c)x\equiv(b/c)\bmod (m/c)$, and that can be helpful for solving congruences. – anon May 18 '13 at 5:17
• @anon sorry I don't understand. Assume the division can be done. What would I need to check for specifically? Do I divide n and d by gcd(n,d) first or something like that? – John Smith May 18 '13 at 5:19
• Yes. You know how to simplify fractions to reduced form? – anon May 18 '13 at 5:20
• Isn't that it? n = n / g, d = d / g where g = gcd(n,d) and n and d are both modulo m – John Smith May 18 '13 at 5:23
• No, $n=n/g$ and $d=d/g$ (with $n,d$ nonzero) are not true unless $g=1$. For example, $4=4/2$ is not true. However $\frac{n}{d}=\frac{n/g}{d/g}$ is true in the rationals - and unless $(m,d)=1$ ($g=\gcd(n,d)$) then it is not true since $n/d$ doesn't make sense mod $m$, like I said. If you begin at a problem that precedes this though - e.g. solving the congruence $ax\equiv b\bmod m$ - you still have options, which I mentioned in the first comment. – anon May 18 '13 at 5:34

If $\gcd(m,d)=g$ and $g\mid n$, then you can perform the standard modular division on $$\left.\frac{n}{g}\middle/\frac{d}{g}\right.\left(\text{mod}\frac{m}{g}\right)\tag{1}$$ Note that the division reduces the modulus, too.

The original equation $$dx\equiv n\pmod{m}\tag{2}$$ is equivalent to $$dx+my=n\tag{3}$$ To solve $(3)$, we need to divide through by $g$: $$\frac{d}{g}x+\frac{m}{g}y=\frac{n}{g}\tag{4}$$ and $x$ in $(4)$ is given by $(1)$.

For example, suppose we know that $$12x\equiv9\pmod{15}$$ we would solve $$4x\equiv3\pmod{5}$$ and any solution would only be known mod $5$; that is, $$x\equiv2\pmod{5}$$

• I don't have the full n necessarily so I don't think I can reliably verify that g divides n – John Smith May 18 '13 at 6:26
• @JohnSmith: if $g\not\mid n$, then you cannot perform the division. That is, there is no solution to $(2)$. – robjohn May 18 '13 at 6:35
• How do I find g if I only have n mod m and d? – John Smith May 18 '13 at 6:35
• @JohnSmith: as I mention above, $g=\gcd(m,d)$. If $g\not\mid n$, then the division is not possible. – robjohn May 18 '13 at 6:36
• @RajeshR: Note that $39/13\pmod{13}$ is asking for a solution to $13x\equiv39\pmod{13}$, which is any $x$. To use $(1)$, we have $g=(13,13)=13$. Thus, we want $x\equiv3/1\pmod{1}$. That is, any $x$ works. – robjohn Jun 23 '18 at 9:08

You are trying to solve the congruence $xd\equiv n \pmod{m}$. Let $e$ be he greatest common divisor of $d$ and $m$. Since $e$ divides $d$ and $m$, if the congruence has a solution, $e$ must divide $n$. If $e$ does not divide $n$, division is not possible.

So let us assume that $e$ divides $n$. Then division is sort of possible, but as we shall see, not entirely satisfactory.

Let $d=d_1e$, $m=m_1e$, and let $n=n_1e$. Then $$xd\equiv n\pmod{m}\quad\text{if and only if}\quad xd_1\equiv n_1\pmod{m_1}.$$ Since $d_1$ and $m_1$ are relatively prime, the congruence on the right has a unique solution modulo $m_1$, found in the usual way.

Call the solution $x_0$. Then the solutions modulo $m$ are $x_0+im_1$, where $i$ ranges from $0$ to $e-1$. Thus modulo $m$ division is possible, but it has several answers.

• I'm not sure this helps me, technically. I have n and d, which are both modulo m. I don't have their full forms pre-modulus. Am I stuck then? – John Smith May 18 '13 at 5:25
• There is no problem. The answer(s) are the same if you replace $n$ by $n+sm$, and $d$ by $d+tm$. If the wish to divide modulo $m$ comes from some other problem, perhaps it would help if you described that other problem, perhaps as an addendum to this one, perhaps separately. – André Nicolas May 18 '13 at 5:29
• What is s and t? – John Smith May 18 '13 at 5:29
• I am writing a function to handle generalized modular division, it takes parameters n, d, and m, and assumes that n/d results in a whole number (without applying any modulus). That being said, when gcd(d,m)=1 there is no issue just returning n*inverse(d,m) but when gcd(d,m) is not 1, I'm stuck – John Smith May 18 '13 at 5:33
• Arbitrary integers. – André Nicolas May 18 '13 at 5:33