2

How can I express $((a-b)/c) \bmod m$ in terms of $a \bmod m$, $b \bmod m$ and $c \bmod m$?

Marc van Leeuwen
  • 115,048
Jatin
  • 123

1 Answers1

1

Assuming the division is without remainder and that $c$ is relatively prime to $m$, you can just evaluate $(a-b)c^{-1}$ in $\mathbf Z/m\mathbf Z$. If $c$ is not relatively prime with $m$, you cannot deduce the value of $(a-b)/c$ modulo $m$ from the images of $a,b,c$ in $\mathbf Z/m\mathbf Z$ alone.

Marc van Leeuwen
  • 115,048
  • if c is 2 and m is 10^9 + 7, then can I express that in a simple form? Also, what is meant by evaluating in Z/mZ? – Jatin Feb 02 '13 at 08:18
  • 1
    Since that $m$ is odd, it is relatively prime with $2$, and by inspection the inverse of $2$ modulo $m$ is $2^{-1}=5\times10^8+4\in \mathbf Z/m\mathbf Z$. Evaluation in $\mathbf Z/m\mathbf Z$ means computing modulo $m$, so in this case the result is $(500000004\times((a\bmod m)-(b\bmod m)) \bmod m$. – Marc van Leeuwen Feb 02 '13 at 11:37