finding ((a +b)/c)mod m

Question

I would like to calculate:

((a+b)/c)mod m

I would like to know if there is any efficient way since a is too big but b , c and m fit in a simple 32-bit int.

Answer 1

There is no division operator in modular arithmetic. Instead, you must calculate the modular inverse of the denominator, then multiply. Thus, in your example, you would calculate a+b modulo m, calculate the modular inverse of c modulo m, then multiply the two modulo m. The modular inverse can be found using the extended Euclidean algorithm. If you don't know how to compute the modular inverse, ask.