I don't know how to prove the following:
Let $a$ be randomly chosen out of $\{ 1,..., p-1\}$ and $b$ randomly chosen out of $\{ 0,..., p-1\}$. Let $m$ be a natural number smaller than a prime number $p$. Let $ h_{a,b}:$ $\{ 0,..., p-1\} \to \{0, ..., m-1 \}$ which is defined as $ h_{a,b} = (ax + b \mod p) \mod m$. Prove for all natural numbers $x, y$ with $x < y < p$: $ P_{a,b}(h_{a,b}(x)=h_{a,b}(y)) \le \frac{1}{m}$ where $P$ is the probability.
Let $k_{a,b}(x) = ax + b \bmod{p}$. If $x \neq y$ then $k_{a,b}(x), k_{a,b}(y)$ is a random pair of distinct numbers in $\{0,\ldots,p-1\}$. Therefore we have reduced your question into the following one:
Show that if $x \neq y$ are random distinct numbers in $\{0,\ldots,p-1\}$, then $$\Pr[x \bmod m = y \bmod m] \leq \frac{1}{m}.$$
Suppose that $p = dm + r$, where $1 \leq r \leq m-1$. Then $\Pr[x \bmod m = c]$ is either $d/p$ (for $c \ge r$) or $(d+1)/p$ (for $c < r$). It follows that $$ \Pr[x \bmod m = y \bmod m] = r \frac{(d+1)d}{p(p-1)} + (m-r) \frac{d(d-1)}{p(p-1)} = \frac{(p-m+r)d}{p(p-1)}. $$ Since $r < m$, we have $\frac{p-m+r}{p-1} \leq 1$. Also, $\frac{d}{p} \leq \frac{d}{dm} = \frac{1}{m}$. Altogether, we obtain an upper bound of $\frac{1}{m}$.
