# How to do division of two numbers which are already under modulo 'm'? [duplicate]

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

• 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. – Angina Seng Dec 7 '19 at 14:14
• 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. – user645636 Dec 7 '19 at 17:16

## 1 Answer

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

• 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. – Bill Dubuque Dec 7 '19 at 16:30