5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – anon May 18 '13 at 5:17
  • $\begingroup$ @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? $\endgroup$ – John Smith May 18 '13 at 5:19
  • $\begingroup$ Yes. You know how to simplify fractions to reduced form? $\endgroup$ – anon May 18 '13 at 5:20
  • $\begingroup$ Isn't that it? n = n / g, d = d / g where g = gcd(n,d) and n and d are both modulo m $\endgroup$ – John Smith May 18 '13 at 5:23
  • $\begingroup$ 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. $\endgroup$ – anon May 18 '13 at 5:34
3
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ I don't have the full n necessarily so I don't think I can reliably verify that g divides n $\endgroup$ – John Smith May 18 '13 at 6:26
  • 1
    $\begingroup$ @JohnSmith: if $g\not\mid n$, then you cannot perform the division. That is, there is no solution to $(2)$. $\endgroup$ – robjohn May 18 '13 at 6:35
  • $\begingroup$ How do I find g if I only have n mod m and d? $\endgroup$ – John Smith May 18 '13 at 6:35
  • $\begingroup$ @JohnSmith: as I mention above, $g=\gcd(m,d)$. If $g\not\mid n$, then the division is not possible. $\endgroup$ – robjohn May 18 '13 at 6:36
  • 1
    $\begingroup$ @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. $\endgroup$ – robjohn Jun 23 '18 at 9:08
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – John Smith May 18 '13 at 5:25
  • $\begingroup$ 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. $\endgroup$ – André Nicolas May 18 '13 at 5:29
  • $\begingroup$ What is s and t? $\endgroup$ – John Smith May 18 '13 at 5:29
  • $\begingroup$ 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 $\endgroup$ – John Smith May 18 '13 at 5:33
  • $\begingroup$ Arbitrary integers. $\endgroup$ – André Nicolas May 18 '13 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.