Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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 Sep 10 '12 at 14:17
    
@axblount I should multiply inverse modulo of 5 to $a-b$ ?? What would I do after that? –  Rushil Sep 10 '12 at 14:25
    
Ok I think I got it. You could post it as an answer so I can accept it. –  Rushil Sep 10 '12 at 14:30

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.