5

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?

Maazul
  • 2,498
John Smith
  • 837
  • 3
    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 05: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 05:19
  • Yes. You know how to simplify fractions to reduced form? – anon May 18 '13 at 05: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 05: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 05:34
  • @anon I added a comment in the answer below to explain more specifically what I am doing – John Smith May 18 '13 at 05:34
  • You say you're trying to get a program to compute $n/d\bmod m$, but have issue with when $(d,m)\ne1$. Note that $n/d$ doesn't make sense when interpreted directly literally modulo $m$. You can't compute something that doesn't make sense. However, you can rephrase the problem more productively: the program is to solve for the integers $x$ such that $xd\equiv n\bmod m$ or state when it has no solution. This is covered in Andre's answer. – anon May 18 '13 at 05:39
  • @anon I don't understand the answer. All I know is that I can compute a bunch of n/d's directly and apply mod m at the very end, and get some result X mod m. But then when I try to do a bunch of n mod m times inverse(d,m) mod m's, I do not get X mod m. Sometimes gcd(d,m) is 1 and sometimes it isn't, so I assume this is why my results differ. – John Smith May 18 '13 at 05:41
  • inverse(d,m) doesn't exist when gcd(d,m) isn't 1. On Andre's answer, speak up about what you don't understand. Specify actual, particular sentences that you don't understand. – anon May 18 '13 at 05:45
  • @anon I don't understand how it applies to what I am trying to do. I have n mod m. I have d mod m. I want to return the same number I would have gotten had I done n / d then modulo m at the end. – John Smith May 18 '13 at 05:46
  • If $(d,m)=1$ then $x=n/d\bmod m$ is the solution to $xd\equiv n\bmod m$. If $(d,m)\ne1$ then $n/d\bmod m$ doesn't make sense (so you cannot compute it), however you can still find the solutions to $xd\equiv n\bmod m$ (which may still exist) or find when none exist. – anon May 18 '13 at 05:48
  • Alternatively, what you might want is to reduce the fraction $n/d$ then compute it $\bmod m$. So you'll want to do $\frac{n}{\gcd(n,m)}$ times the inverse of $\frac{d}{(d,m)}$ - this can be done precisely when $xd\equiv n\bmod m$ has a solution. However the result of this computation will not give all solutions to said congruence, so theoretically it seems inadequate. – anon May 18 '13 at 05:52
  • @anon I feel like we are talking past each other. It does make sense because every single n/d results in a whole number that I can then apply modulo m to. You can take any integer and apply modulo m to it. For example I can do 100/4 modulo 10 which gives me 5. So now let's say I have n= 100 mod 10 = 0 and d = 4 mod 10 = 4. I now want to somehow get 5, only armed with n=0, d=4, and m=10. I can't do (0*inverse(4,10)) mod 10 – John Smith May 18 '13 at 05:52
  • Every single $n/d$ results in a whole number? So $2/3,4/5,6/5$ etc. are all whole numbers? – anon May 18 '13 at 05:53
  • I wouldn't call the modular division function on those types of numerators and denominators. My function is meant for n and d such that n % d = 0, or when d divides n – John Smith May 18 '13 at 05:54
  • So $n$ was a multiple of $d$ all along and you didn't tell us? In such a circumstance you can simply divide $n$ by $d$ before reducing mod $m$. (Doing the division $\bmod m$ is not possible when $(d,m)\ne1$.) Withholding critical information from those you seek help from is always counterproductive. – anon May 18 '13 at 05:55
  • Please note below when I said "it takes parameters n, d, and m, and assumes that n/d results in a whole number (without applying any modulus)" – John Smith May 18 '13 at 05:55
  • And again please assume I do not have n and d in full. I am trying to find the answer assuming n and d have already been reduced. Sometimes it isn't possible to have them in full form because I can only calculate them modulo m (for example a very large modular exponent) – John Smith May 18 '13 at 05:56
  • Sorry for not reading carefully. If you do not have $n$ or $d$ in full (only their residues) then your problem is hopeless. For instance, suppose you want to do things mod $100$. If $n=200$ and $d=40$ then $200/20=10$. Similarly $n=100$ and $d=20$ yields a quotient of $100/20=5$. But $5$ and $10$ are different, and in either case the only thing you're given are the residues $0$ and $20$ mod $100$. There is no unique answer for the whole number quotient $n/d$ given only the residues of $n$ and $d$ mod $m$ in general. – anon May 18 '13 at 06:00
  • What if I have d in full? – John Smith May 18 '13 at 06:01
  • My example covers that too. – anon May 18 '13 at 06:02
  • @anon No I mean if I have n mod m, and d (no mod), wanting to find n / d mod m – John Smith May 18 '13 at 06:02
  • I know. If I told you $n\bmod 100$ was $0$ and told you $d=20$ (no modulus) then you would not be able to tell the difference between $100/20=5$ and $200/20=10$; there is not a unique answer. – anon May 18 '13 at 06:04
  • @anon what if I use chinese remainder theorem to break up the modulus into prime powers? – John Smith May 18 '13 at 06:18
  • Then you would have the modulus factorized into prime powers. – anon May 18 '13 at 06:28
  • @anon It was a useless thought, I was thinking that if the moduli were prime then they'd for sure be coprime to the denominators but that's false – John Smith May 18 '13 at 06:30

2 Answers2

3

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

robjohn
  • 345,667
  • 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 06:26
  • 1
    @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 06:35
  • How do I find g if I only have n mod m and d? – John Smith May 18 '13 at 06: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 06:36
  • So even if I only have n mod m, I should be able to do (n mod m)/g? – John Smith May 18 '13 at 06:37
  • @JohnSmith: if $g\mid m$ then $g\mid(n+km)$ for any $k\in\mathbb{Z}$ iff $g\mid n$. – robjohn May 18 '13 at 06:40
  • What if we have (39/13) mod 13 ? Answer should be 3. But if divide by gcd(13,13), then we get (3/1)mod 1. What to do next? – Ramesh Jun 23 '18 at 04:57
  • 1
    @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 09:08
  • @robjohn, Thank you. Actually when writing the program, I write (39/13)mod 13 as (39mod13 * inverse (13)mod13)mod13 which is (0*a)mod13 and a(or inverse of 13 mod 13) doesn't exist and I get zero as the answer. I am stuck here now. – Ramesh Jun 24 '18 at 09:09
  • @RajeshR: how do you multiply by something that doesn't exist and get something that does? – robjohn Jun 24 '18 at 12:23
  • @robjohn , Yaa, that's where I am stuck. Actual answer to the question is 3 as (39/13)mod13 is 3mod13 is 3. But I am not able to get this answer using inverse modulo method. – Ramesh Jun 24 '18 at 13:15
1

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.

André Nicolas
  • 507,029
  • 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 05: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 05:29
  • What is s and t? – John Smith May 18 '13 at 05: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 05:33
  • Arbitrary integers. – André Nicolas May 18 '13 at 05:33
  • If you want a single answer, it will be $n_1\times \text{inverse}(d_1,m_1)$, where $n_1,d_1,m_1$ are as in my answer. Unfortunately, the answer is modulo $m_1$, and becomes several answers modulo $m$. As a simple example, when you divide $3$ by $9$ (yes, I mean it) modulo $12$, you are solving $9x\equiv 3\pmod{12}$, which is equivalent to $3x\equiv 1\pmod{4}$. This has the solution $x\equiv 3\pmod{4}$, giving mod $12$ the solutions $3$, $7$, and $11$. – André Nicolas May 18 '13 at 05:40