Simple question about number theory in CLRS book This is theorem 11.5 from CLRS book. Suppose a

Frank Day

Frank Day

Answered question

2022-07-09

Simple question about number theory in CLRS book
This is theorem 11.5 from CLRS book. Suppose a Z p , b Z p .
Consider two distinct keys k and l from Z p , so that k l. For a given hash function h a b we let
r = a k + b mod p
s = a l + b mod p
We first note that r s. Why? Observe that
r s a ( k l ) ( mod p ) .
I'm not very well familiar with Number Theory, so my question is why r s a ( k l ) ( mod p ) is correct?

Answer & Explanation

Dobermann82

Dobermann82

Beginner2022-07-10Added 15 answers

Step 1
According to Knuth's definition for the mod operation, we have a mod n = a n a n
And with the general definition of Congruence, a b ( mod n ) can be rewritten as a b = k n .
We then have r = a k + b mod p = a k + b p a k + b p s = a l + b mod p = a l + b p a l + b p
Subtract r by s, we have
(A) r s = a ( k l ) p ( a k + b p + a l + b p )
With the definition of congruence quoted above, we can then rewrite (A) as r s a ( k l ) ( mod p ) .
Hope this eliminates your doubts.
daktielti

daktielti

Beginner2022-07-11Added 2 answers

Explanation:
I’m turning my comment into an answer. If r = a k + b mod p, and s = a l + b mod p, then r s = ( a k + b ) ( a l + b ) mod p, thus r s = a k a l mod p, hence r s = a ( k l ) mod p.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?