First, consider choosing $x$ and $y$ from $0$, $1$, $\cdots$, $\lfloor{\sqrt{p}}\rfloor$. There are $\left(\lfloor{\sqrt{p}}\rfloor + 1\right)^2$ possible pairs. The number is more than $p$. Therefore, as $(x, y)$ varies over these possible combinations, there will be more than $p$ expressions in the form of $(ax - y)$. By the pigeonhole principle, there must be at least two such expressions are congruent to each other modulo $p$. Let them be $(x_1, y_1)\ne (x_2, y_2)$, but $ax_1 - y_1 \equiv ax_2 - y_2\pmod{p}$. This implies $a(x_1 - x_2) \equiv (y_1 - y_2)\pmod{p}$. Let $x=\mid x_1 - x_2\mid$ and $y=\mid y_1 - y_2 \mid$, we will have $ax \equiv \pm y\pmod{p}$.

All left to do is to exclude the possibility that $x=0$ or $y=0$. If so, both $x$ and $y$ will be in the required range.

If $x=0$, then $x_1 = x_2$ and $a(x_1 - x_2) = 0 \equiv y_1 - y_2 \pmod{p}$. Because $0 \le y_1, y_2 < p$, then it must hold that $y_1 = y_2$. This contradicts to the assumption of $(x_1, y_1)\ne (y_1, y_2)$.

Meanwhile, if $y=0$, then $y_1 = y_2$ and $a(x_1 - x_2)\equiv 0\pmod{p}$. Because $p$ is a prime and $p\not\mid a$, this means that $x_1 - x_2\equiv 0\pmod{p}$. By applying the similar logic stated previously, this will also lead to the same contradiction.