Modular arithmetic - integer's remainder computed iteratively

Question

When reading about Rabin-Karp's algorithm for substring search I've found that, for example:

$312 \bmod 13$

can be calculated also as:

$[10*([10*([10 * 0 + 3] \bmod 13) + 1] \bmod 13) + 2] \bmod 13$

How can I prove that's correct? What properties of modular arithmetic have been applied here?

Answer 1

If $m$, $n$ are integers with $m \ge 0$, $n > 0$, $m \mathop{\mathsf{mod}}n$ is defined to be the unique integer $r$ with $0 \le r < d$ such that there exists a $d$ with $$ m = dn + r. $$

If you also have: $$ m' = d' n + r' $$ with $0 \le r < n$, then you have:

$$ m + m' = (d + d')n + (r + r'). $$ There are now two cases: if $r + r' < n$, then, by definition, you have $$(m + m')\mathop{\mathsf{mod}}n = r + r' = (r + r')\mathop{\mathsf{mod}} n. $$

If, on the other hand, $r + r' \ge n$, then $r + r' < 2n$ and so (by the definition) you will have: $$ r + r' = n + ((r + r') \mathop{\mathsf{mod}} n), $$ and then: $$ m + m' = (d + d' + 1)n + ((r + r') \mathop{\mathsf{mod}} n), $$ which (as $0 \le (r + r') \mathop{\mathsf{mod}} n < n$ shows that: $$ (m + m') \mathop{\mathsf{mod}} n = (r + r') \mathop{\mathsf{mod}} n. $$

So in either case you can compute $(m + m') \mathop{\mathsf{mod}} n$ by computing $r = m \mathop{\mathsf{mod}} n$ and $r' = m' \mathop{\mathsf{mod}} n$, and then computing $(r + r') \mathop{\mathsf{mod}} n$. A similar argument shows that the same approach will work for computing $(m m') \mathop{\mathsf{mod}} n$.

If $m$ or $n$ can be negative, be careful, because different people (and programming languages) adopt different conventions for the definition of $m \mathop{\mathsf{mod}} n$ in that case. I expect that doesn't apply to the algorithm you are studying.

Answer 2

This looks very much like Horner's scheme for polynomial evaluation: this number (in base $10$ can be written as $$[312]_{10}=2\cdot 10^2+1\cdot 10^1+2\cdot 10^0. $$ Now consider the polynomial $$P(x)=3x^2+x+2$$ Horner's scheme is the algorithmic translation of the following rewriting of this polynomial with parentheses: $$P(x)=\bigl((3x+1)x+2\bigr)$$ and $312=P(10)$. You obtain the value mod $13$ reducing at each step of the computation mod $13$.