0
$\begingroup$

How to do division for the following example?

Case 1 : Without modulo

n1 = 40, n2 = 8

Quotient = n1/n2 = 5


Case 2 : With modulo

m = 6

n1 = n1 mod m = 4 (AND) n2 = n2 mod m = 2

Quotient = 4 / 2 = 2

Now,In case 1, Quotient = 5, but in case 2, Quotient = 2. How to do division on numbers such that both numbers are already under modulo 'm'?

$\endgroup$
2
  • 1
    $\begingroup$ I presume you are aiming to solve the congruence $n_2x\equiv n_1\pmod m$? One solves such linear congruences using the Euclidean algorithm. $\endgroup$ – Angina Seng Dec 7 '19 at 14:14
  • $\begingroup$ 5 is also a possible answer in mod 6. 4 is congruent to -2 so dividing that by 2 you get -1 which is congruent to 5. $\endgroup$ – user645636 Dec 7 '19 at 17:16
-2
$\begingroup$

This only works if $m$ is a prime and thus the group of residues is a field. If $m$ is not prime, the corresponding congruences modulo $m$ don't have unique solutions.

In your case, the “quotient” $x\equiv4/2$ corresponds to the congruence $2x\equiv4$. Modulo $6$, this congruence has two different solutions, $x=2$ and $x=5$. More generally, if $m$ is not prime and $a$ in $ax\equiv b$ is not coprime with $m$, then the solution is only fixed up to multiples of $m/\gcd(a,m)$.

$\endgroup$
1
  • $\begingroup$ Modular fraction arithmetic is not restricted to prime moduli. Rather it is restricted to fractions writable with denominator coprime to the modulus - see the linked dupes. $\endgroup$ – Bill Dubuque Dec 7 '19 at 16:30

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