How to do division of two numbers which are already under modulo 'm'?

56 Views Asked by At

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'?

1

There are 1 best solutions below

1
On

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)$.