Problem 1566

Consider the set formed by $mt + u$ when $t, u$ take all the $[\sqrt{p}] + 1$ integers $0, 1, \cdots, [\sqrt{p}]$. Since $t$ and $u$ each take $[\sqrt{p}] + 1$ values, this results in $([\sqrt{p}] + 1)^2$ values of $mt + u$. Note that
$$([\sqrt{p}] + 1)^2 > (\sqrt{p})^2 = p$$
Thus, there are at least two pairs of numbers $t_1, u_1$ and $t_2, u_2$ such that $mt_1 + u_1 \equiv mt_2 + u_2 \pmod{p}$, i.e.,
$$mt_1 + u_1 \equiv mt_2 + u_2 \pmod{p}$$

Since $t_1, u_1$ and $t_2, u_2$ are two distinct pairs of numbers, it cannot be the case that
$$t_1 = t_2, u_1 = u_2$$

(1) If $t_1 = t_2$, then (5) becomes
$$u_1 \equiv u_2 \pmod{p}$$

Assume $u_1 \geqslant u_2$, then $0 \leqslant u_1 - u_2 \leqslant [\sqrt{p}]$. Let $t_1 - t_2 = x, u_2 - u_1 = y$, then we have
$$1 < x < [\sqrt{p}] < \sqrt{p}, 1 < |y| \leqslant [\sqrt{p}] < \sqrt{p}$$

and
$$mx \equiv y \pmod{p}$$

This is exactly what we need to prove.
Now we can proceed to prove the main result of this section.