Frank Day

2022-07-09

Simple question about number theory in CLRS book
This is theorem 11.5 from CLRS book. Suppose $a\in {\mathbb{Z}}_{p}^{\ast },b\in {\mathbb{Z}}_{p}$.
Consider two distinct keys k and l from ${\mathbb{Z}}_{p}$, so that $k\ne l$. For a given hash function ${h}_{ab}$ we let
$r=ak+b\phantom{\rule{1em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}p$
$s=al+b\phantom{\rule{1em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}p$
We first note that $r\ne s$. Why? Observe that
$r-s\equiv a\left(k-l\right)\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}p\right).$
I'm not very well familiar with Number Theory, so my question is why $r-s\equiv a\left(k-l\right)\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}p\right)$ is correct?

Dobermann82

Expert

Step 1
According to Knuth's definition for the mod operation, we have $\begin{array}{r}amodn=a-n⌊\frac{a}{n}⌋\end{array}$
And with the general definition of Congruence, $a\equiv b\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n\right)$ can be rewritten as $\begin{array}{r}a-b=kn\end{array}$.
We then have $\begin{array}{rl}r& =ak+bmodp=ak+b-p⌊\frac{ak+b}{p}⌋\\ s& =al+bmodp=al+b-p⌊\frac{al+b}{p}⌋\end{array}$
Subtract r by s, we have
$\begin{array}{}\text{(A)}& r-s=a\left(k-l\right)-p\left(⌊\frac{ak+b}{p}⌋+⌊\frac{al+b}{p}⌋\right)\end{array}$
With the definition of congruence quoted above, we can then rewrite (A) as $\begin{array}{r}r-s\equiv a\left(k-l\right)\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}p\right)\end{array}$.

daktielti

Expert

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

Do you have a similar question?