, 2016

Consider all numbers of the form $a + b k$ where $a, b$ are integers with $0 \le a, b < \sqrt{p}$. Since there are more than $(\sqrt{p})^2 = p$ numbers, by the pigeonhole principle, two of them must be congruent modulo $p$. Their difference, which is of the form $c + d k$ with $|c|, |d| < \sqrt{p}$ and $(c, d) \ne (0, 0)$, is divisible by $p$. Now, note that
$$(c + d k)(c - d k) = c^2 - d^2 k^2 \equiv c^2 + 5 d^2 \pmod{p}.$$
Therefore, $p \mid c^2 + 5 d^2$. Since
$$0 < c^2 + 5 d^2 < p + 5p = 6p,$$
we must have $c^2 + 5 d^2 = r p$ with $r = 1, 2, 3, 4, 5$.

* If $c^2 + 5 d^2 = p$, then
$$(c^2 - 5 d^2)^2 + 5 (2 c d)^2 = (c^2 + 5 d^2)^2 = p^2.$$
Clearly, $c, d \ne 0$. So we can take $(m, n) = (|c^2 - 5 d^2|, 2|c d|)$.

* If $c^2 + 5 d^2 = 2p$, then $c, d$ are odd as $2p \equiv 2 \pmod{4}$. Therefore, we have
$$\left(\frac{c^2 - 5 d^2}{2}\right)^2 + 5 (c d)^2 = \left(\frac{c^2 + 5 d^2}{2}\right)^2 = p^2.$$
So we can take $(m, n) = \left(\left|\frac{c^2 - 5 d^2}{2}\right|, |c d|\right)$.

* If $c^2 + 5 d^2 = 3p$, then $3 \mid c \pm d$ as $9 \mid 3p$. Therefore, $3 \mid c \pm d$ for some choice of the sign. Then we have
$$\left( \frac{c \mp 5 d}{3} \right)^2 + 5 \left( \frac{c \pm d}{3} \right)^2 = \frac{2(c^2 + 5 d^2)}{3} = 2p$$
with $\frac{c \mp 5 d}{3}$ and $\frac{c \pm d}{3}$ nonzero. Thus, this is reduced to the second case.

* If $c^2 + 5 d^2 = 4p$, then $c, d$ are even. Therefore, we have
$$\left(\frac{c}{2}\right)^2 + 5\left(\frac{d}{2}\right)^2 = p,$$
which is reduced to the first case.

* If $c^2 + 5 d^2 = 5p$, then $5 \mid c$. Therefore, we have
$$d^2 + 5 \left( \frac{c}{5} \right)^2 = p,$$
which is reduced to the first case.

Since all cases are exhausted, we are done.