I'm studying the Rabin Karp algorithm and something isn't clear about the modulus algebra:
Let's suppose I have all base-10 numbers for simplicity's sake
$14159 = (31415 - 3 \cdot 10^4) \cdot 10 + 9$
now if I apply the modulus operation ($\bmod 997$) to each term I get:
$201 = [ (508 - 3 \cdot 30) \cdot 10 +9 ] \bmod 997$
but in the algorithm I'm studying there is this line:
$201 = [ (508 + 3 \cdot (997-30)) \cdot 10 +9] \bmod 997$
interestingly to me, the result is the same: $201$.
Why do they used the second version? Is there something I'm not considering and the $3 \cdot 997 \cdot 10$ term is useful to something?
Edit: I was wondering... does adding a large prime number (like 997) has some algorithmic implications?