Finding a / b mod c

Question

I know this may seem like a mathematical question, but I just saw it in a contest and I really want to know how to solve it.

We have

a (mod c)

and

b (mod c)

and we are looking for the meaning of private

(a / b) (mod c)

Any ideas?

Answer 1

In the ring of integers modulo C these equations are equivalent:

A / B (mod C)
A * (1/B) (mod C)
A * B ¹ (mod C) .

So you need to find B ^{-1 the} multiplicative inverse of B modulo C You can find it, for example, the advanced Euclidean algorithm.

Note that not every number has a multiplicative inverse for a given module.

In particular, B ^-1 exists if and only if gcd(B, C) = 1 (i.e., B and C are coprime).

see also

• Wikipedia / Modular Multiplicative Reverse
• Wikipedia / Advanced Euclidean Algorithm

---

Modular Multiplicative Reverse: Example

Suppose we want to find the multiplicative inverse of 3 modulo 11.

That is, we want to find

x = 3 ¹ (mod 11)
x = 1/3 (mod 11)
3x = 1 (mod 11)

Using the advanced Euclidean algorithm, you will find that:

x = 4 (mod 11)

Thus, modular multiplicative inversion 3 modulo 11 is 4. In other words:

A / 3 == A * 4 (mod 11)

---

Naive algorithm: brute force search

One way to solve this problem:

3x = 1 (mod 11)

Just try x for all values ​​of 0..11 and see if this equation is true. For a small module, this algorithm may be acceptable, but the extended Euclidean algorithm is much better asymptotically.

Answer 2

There are potentially many answers. When all you have is k = B mod C, then B can be any k + CN for the whole integer N.

This means that B could potentially be very large. In fact, so large as to bring A / B closer to zero.

However, this is just one way to answer.

Answer 3

I think it can be written as (but not sure)

 (a/b)%c = ((a)%(b*c))/b