Modular arithmetic - integer's remainder computed iteratively 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?
 A: 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.
A: 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$.
