# modular arithmetic in rolling hash algorithm

My question was around the rolling hash function in RobinKarp algorithm. It is intuitive for me to understand how to get from xi to xi+1 without the mod, however with the mod i am not sure how we still get the right answer. Is there any mathematical theroem anyone could quote which would help me understand?

So i get,

xi = (ti)R^0 + (ti+1)R^1 + .. + (ti+m-1)R^M-1
xi+1 = (xi - (ti)R^0)/R + (ti+m)R^M


but whats the guarantee,

xi = [ (ti)R^0 + (ti+1)R^1 + .. + (ti+m-1)R^M-1 ] mod Q
xi+1 = [ (xi - (ti)R^0)/R + (ti+m)R^M ] mod Q


.. and so on will be correct even after introducing mod Q

Pretty sure its some basic mod arithmetic theorem i am missing here.

What you are missing is the identity $$(a + b) \bmod{Q} = (a \bmod{Q} + b \bmod{Q}) \bmod{Q}.$$
With the modular arithmetic, the division by R is possible because R and Q are chosen such that $\gcd(R, Q) = 1$, therefore R has a modular multiplicative inverse modulo Q and can always be divided by. As a bonus, dividing by R becomes a multiplication, which is easier than integer division even if it is by a constant.