模算术迭代计算整数余数的正确性证明及所涉性质（Rabin-Karp场景）

Great question—this iterative modulus calculation is exactly the trick that makes Rabin-Karp's rolling hash so efficient for substring searches! Let's break down why this method works, step by step.

Proof of Correctness #

First, let's formalize what's happening here. The number 312 can be written as a weighted sum of its digits:
$$312 = 3 \times 10^2 + 1 \times 10^1 + 2 \times 10^0$$

The iterative calculation you're using builds this sum incrementally, taking the modulus at each step. Let's generalize this to any number with digits $d_0d_1d_2...d_n$ (where $d_0$ is the leftmost digit) and modulus $m$:

1. Start with current = 0
2. For each digit $d_i$:
   $$current = (10 \times current + d_i) \mod m$$
3. The final current equals the entire number mod $m$.

We can prove this with mathematical induction:

Base Case (1 digit) #

If we have a single digit $d_0$, the iterative step gives:
$$current = (10 \times 0 + d_0) \mod m = d_0 \mod m$$
Which is exactly the value of the number itself mod $m$. The base case holds.

Inductive Step #

Assume the formula works for a $k$-digit number $N_k = d_0d_1...d_{k-1}$, meaning:
$$current_k = N_k \mod m$$
where $current_k$ is the result after processing the first $k$ digits.

Now consider the $(k+1)$-digit number $N_{k+1} = N_k \times 10 + d_k$. The next iterative step computes:
$$current_{k+1} = (10 \times current_k + d_k) \mod m$$

By the inductive hypothesis, substitute $current_k = N_k \mod m$:
$$current_{k+1} = (10 \times (N_k \mod m) + d_k) \mod m$$

Using modular arithmetic properties (we'll cover these next), this simplifies to:
$$current_{k+1} = (10 \times N_k + d_k) \mod m = N_{k+1} \mod m$$

This proves the formula works for all digit lengths. For your example with 312 and $m=13$:

• After first digit: $(10*0 +3) \mod13 =3$
• After second digit: $(10*3 +1) \mod13 =31 \mod13=5$
• After third digit: $(105 +2) \mod13=52 \mod13=0$
  Which matches $312 \mod13=0$ (since $1324=312$).

Key Modular Arithmetic Properties Used #

This method relies on two fundamental properties of modular arithmetic, which let us safely take the modulus at each step without changing the final result:

1. Addition Modulo $m$:
   $$(a + b) \mod m = [(a \mod m) + (b \mod m)] \mod m$$
   This means adding two numbers and then taking the modulus is the same as taking each number's modulus first, adding them, then taking the modulus again.

2. Multiplication Modulo $m$:
   $$(a \times b) \mod m = [(a \mod m) \times (b \mod m)] \mod m$$
   Similarly, multiplying two numbers and taking the modulus is equivalent to taking each modulus first, multiplying, then taking the modulus again.

Combined, these give us the critical property for our iterative step:
$$(a \times b + c) \mod m = [(a \mod m) \times (b \mod m) + (c \mod m)] \mod m$$

In plain terms: whenever you're computing a linear combination (like multiplying the current sum by 10 and adding the next digit), you can take the modulus at any point to keep numbers small—this won't affect the final result. This is essential in Rabin-Karp because it prevents integer overflow when dealing with very long strings (which we treat as large numbers).

内容的提问来源于stack exchange，提问作者Apple Pie