2
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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