Q:

Modular Arithmetic - Division

How does one calculate (a/b) % m where a = x1*x2*.... and the numbers x1, x2,.. are quite large.
If we only had to find a % m , we could have easily done that using (x1%m) * (x2%m) *... but if there's something in the denominator 'b' in our case, how does one go about calculating it ?
I read somewhere this being done as (a % (m*b)) / b . I have been wondering if this is true and how do we go about proving it ?  

A:

You can get at least this far:
b * ((a / b) % m) = (b * (a / b)) % (b * m)
                  = (a - (a % b)) % (b * m)
                  = (a % (b * m) - (a % b) % (b * m))
                  = (a % (b * m) - (a % b))

hence,

((a / b) % m) = ((a % (b * m)) - (a % b)) / b

That is already easier to compute, hence I justify giving this as an answer.  I think you can go on from there to the simpler formula you suggested, but I haven't the time or inclination to work that out.  (So if this is homework then I leave a bit of it for you to do yourself :))

