I know this may seem like a math question but i just saw this in a contest and I really want to know how to solve it.
We have
a (mod c)
and
b (mod c)
and we're looking for the value of the quotient
(a/b) (mod c)
Any ideas?
In the ring of integers modulo C
, these equations are equivalent:
A / B (mod C)
A * (1/B) (mod C)
A * B
-1(mod C)
.
Thus you need to find B
-1, the multiplicative inverse of B
modulo C
. You can find it using e.g. extended Euclidian algorithm.
Note that not every number has a multiplicative inverse for the given modulus.
Specifically, B
-1 exists if and only if gcd(B, C) = 1
(i.e. B
and C
are coprime).
Suppose we want to find the multiplicative inverse of 3 modulo 11.
That is, we want to find
x = 3
-1(mod 11)
x = 1/3 (mod 11)
3x = 1 (mod 11)
Using extended Euclidian algorithm, you will find that:
x = 4 (mod 11)
Thus, the modular multiplicative inverse of 3 modulo 11 is 4. In other words:
A / 3 == A * 4 (mod 11)
One way to solve this:
3x = 1 (mod 11)
Is to simply try x
for all values 0..11
, and see if the equation holds true. For small modulus, this algorithm may be acceptable, but extended Euclidian algorithm is much better asymptotically.
B = 0 (mod C)
means B
and C
are not coprimes. Inverse does not exist in this case.
Aug 20, 2010 at 17:49
There are potentially many answers. When all you have is k = B mod C, then B could be any k+CN for all integer N.
This means B could potentially be very large. So large, in fact, to make A/B approach zero.
However, that's just one way to respond.
I think it can be written as(But not sure)
(a/b)%c = ((a)%(b*c))/b
/
changes its definition when mod
is involved.
a/b
is the same asa * (1/b)
where(1/b)
is the multiplicative inverse ofb
in the group Z (mod c).BigInteger.modInverse
. You can also implement extended Euclidian algorithm yourself for instructional purposes.