Modular arithmetic (a*b/e)%m?

Question

Is there a modular expression possible for following :

((a*b)/e)%m

For ex :

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

Answer 1

Instead of performing division when using modular arithmetic, you must multiply by the modular inverse. For instance, to divide by e, you would multiply by the modular inverse c where c × e ≡ 1 (mod m). You can calculate the modular inverse of x (mod m) by the following algorithm:

function inverse(x, m)
    a, b, u = 0, m, 1
    while x > 0
        q = b // x # integer division
        x, a, b, u = b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

Thus, for your expression ((a*b)/e)%m you would compute (a * b * inverse(e,m)) % m.

Answer 2

It depends on what you mean for division; for example for

a = 1
b = 1
e = 3
m = 7

what is the result you expect? 1/3 is 0 by conventional arithmetic, if it's that what you're looking for in this case then there is no shortcut in general (you can however trade the division for a multiplication and a shift if a*b is known to be small enough).

Another option for division x/y is however looking for the number that multiplied by y gives x in modular arithmetic (and 1/3 with this meaning is 5 because 5*3 is 1 when thinking modulo 7). If this is what you're looking for instead of dividing by e you can multiply by the modular inverse of e i.e. for the number that multiplied by e gives 1 (mod m).