Simple question about number theory in CLRS bookThis 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 pWe 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?

Question

Simple question about number theory in CLRS bookThis 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      pWe first note that   r  ≠  s. Why? Observe that  r  −  s  ≡  a  (  k  −  l  )    (  mod    p  )  .I&#039;m not very well familiar with Number Theory, so my question is why   r  −  s  ≡  a  (  k  −  l  )    (  mod    p  ) is correct?

Dobermann82 · Accepted Answer

Step 1According to Knuth&#039;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 · Accepted Answer

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.