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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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

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

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

share|cite|improve this answer

Your Answer


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.