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.

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|improve this question
add comment

2 Answers 2

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|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
add comment

$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|improve this answer
add comment

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.