Let $p$ a prime number of the form $p = 4k + 1$ for $k \in \mathbb{N}$ and let $a \in \mathbb{N}$ be such that $a^2 + 1$ is a multiple of $p$.
We denote $r$ the integer part of the number $\sqrt{p}$ and $E$ the set $\{0, 1, \dots, r\}$.
Show that there are two distinct pairs $(x, y)$ and $(x', y')$ of $E^2$ for which the two natural integers $x + ay$ and $x'+ ay'$ have the same remainder of the Euclidean division on $p$.
Consider the function $f(x,y)=x+ay;0\le x,y\le r$. There are $(r+1)^2$ distinct ordered pairs $(x,y)$. But $r=\lfloor\sqrt p\rfloor<\sqrt p<\lfloor\sqrt p\rfloor+1=r+1$. Thus, $(r+1)^2>p$, which means we have more ordered pairs than numbers in the canonical residue system of $p$. Thus, when we see $f(x,y)\mod p$, there must be at least two distinct pairs $(x,y),(x',y')$ such that $f(x,y)\equiv f(x',y')\mod p$.