Simple question about number theory in CLRS bookThis is theorem 11.5 from CLRS book. Suppose...
Simple question about number theory in CLRS book
This is theorem 11.5 from CLRS book. Suppose .
Consider two distinct keys k and l from , so that . For a given hash function we let
We first note that . Why? Observe that
I'm not very well familiar with Number Theory, so my question is why is correct?
Answer & Explanation
According to Knuth's definition for the mod operation, we have
And with the general definition of Congruence, can be rewritten as .
We then have
Subtract r by s, we have
With the definition of congruence quoted above, we can then rewrite (A) as .
Hope this eliminates your doubts.
I’m turning my comment into an answer. If mod p, and mod p, then mod p, thus mod p, hence mod p.