# Problem with Modulus and division

Suppose I want to compute $(a_1 + a_2 + ... + a_n) \mod m$. For very large values of $a_i$, I can take modulo after every operation: $[(a_1 \mod m) + (a_2 \mod m) + ... + a_n \mod m] \mod m$ (I don't want the values to exceed their data-type's size). This doesn't work when there's a division operation in the expression.

Specifically I have this expression: $[(a-b)/5] \mod m$

which is not equal to: $[(a \mod m) - (b \mod m)]/5 \mod m$

because after taking modulo, the numerator will not necessarily be divisible by the denominator ( a-b will always be divisible by 5).

What is the work-around to this problem?

• Instead of dividing by 5, multiply by its inverse modulo $m$. – axblount Sep 10 '12 at 14:16
• inverse modulo? Let me look it up.. – Rushil Paul Sep 10 '12 at 14:17
• @axblount I should multiply inverse modulo of 5 to $a-b$ ?? What would I do after that? – Rushil Paul Sep 10 '12 at 14:25

Assume that $m$ is not divisible by $5$, and let $k$ be an inverse of $5$ modulo $m$. That is, suppose that $5k\equiv 1\pmod{m}$. Then your expression can be rewritten as $(ka-kb) \bmod{m}$.
Finding an inverse of $5$ modulo $m$ requires not much work: one of $m$, $2m$, $3m$, or $4m$ is congruent to $-1$ modulo $5$. Say it is $im$. Then $k=(im+1)/5$.