# Simple modulus algebra - rabin karp weird implementation

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?

-

Hint $\rm\ mod\ 997\!:\ -30\, \equiv\, 997-30.\:$ This is probably done to keep the remainders positive.
Note that $\rm\: 1000\equiv 3\:\Rightarrow\: 31415\, =\ 31\cdot 1000 + 415\,\equiv\, 31\cdot 3 + 415\,\equiv\, 508,$ etc.
@John Though it is often convenient to work with a balanced residue system, e.g. $\rm\:\pm\{0,1,2,3\}\ mod\ 7,\:$ many textbooks (and algorithms) work only with the least positive representatives (remainders). It's usually easy to infer which is being empoyed. For algorithms it is essential to know wich is employed, e.g. for testing equality (congruence), i.e. for reducing to canonical normal forms. –  Bill Dubuque Sep 15 '12 at 17:26