0
$\begingroup$

know some rules for modular arithmetic expressions, for example,

  1. $A+B=C\implies ((A\bmod M) + (B\bmod M))\bmod M = C\bmod M$.

2.$A\times B=C\implies $((A\bmod M)\times (B\bmod M))\bmod M = C\bmod M$.

($A$, $B$, $C$, and $M$ are just constant arbitrary integers)

But I did not understand the following one $$A - B = C \implies ( (A\bmod M)-(B\bmod M)+kM)\bmod M = C\bmod M$$ for some value $k$.

I am interested because, as I know, such methods are used in computing hash values of strings and generally related with string search methods. My question is, what does $k$ do in this case? Can we use arbitrary value of $k$? or how to calculate which value of $k$ is relevant for such calculation? Thanks a lot.

$\endgroup$
1
$\begingroup$

Do you know the meaning of modular arithmetic? If so then you will know that when you do any addition/subtraction/multiplication you might not get an answer that lies in the range 0,1,2,..., M-1 so you might have to manipulate your answer by a multiple of M

$\endgroup$
  • $\begingroup$ so it means that k=n*M?where n is some number? $\endgroup$ – dato datuashvili Mar 9 '12 at 11:48
  • $\begingroup$ No, notice that $k$ only comes up in the context $kM$, so it's a multiplier of $M$, not a multiple of $M$. $\endgroup$ – Gerry Myerson Mar 9 '12 at 11:51
1
$\begingroup$

$M\equiv 0 \pmod{M}$, so $M$ acts like zero in this type of expression. So your expression is demonstrating the modification $$ A-B=C \rightarrow A-B+k*0 = C $$ from which it should be clear that $k$ can be arbitrary.

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