Search code examples
algorithmmathmodular-arithmeticmathematical-expressions

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

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
Solution

  • 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.