https://aops.com/community/p11383321 kaede wrote: Let $a$ be coprime to $p$ and $p>2.$ Since $\sum^{p-1}_{j=1}\left(\frac{a-j^{2}}{p}\right) =-\left(\frac{a}{p}\right) -\left(\frac{-1}{p}\right)$, there exists an integer $y(0<y< p)$ such that $\left(\frac{a-y^{2}}{p}\right) =+1$ when $p>5$. It follows that $x^{2}+y^{2} \equiv a\pmod p$ for $x,y\not\equiv 0\pmod p$ when $p>5$. Note that if $p\equiv 1\pmod 4$, then there exist $x,y\not\equiv 0\pmod p$ satisfying $x^{2}+y^{2} \equiv 0\pmod p$, and that if $p\equiv 3\pmod 4$, then there does not exist $x,y\not\equiv 0\pmod p$ satisfying $x^{2}+y^{2} \equiv 0\pmod p$. The rest is easy.

Actually this problem is quite similar to P5 in the 2017 Autumn Camp of Tsinghua University

. See here.