Austrian Mathematical Olympiad

All $p$ residue classes.

With $a^2+0^2$ we first obtain all quadratic residue classes. Since not all residue classes are quadratic residues, there is a quadratic residue class $a^2$ that is followed by a quadratic non-residue class, so that $n=a^2+1$ is not a quadratic residue and therefore of course $n\ne 0(\mathrm{mod}p)$. However, since the product of two quadratic non-residue classes is a quadratic residue class, it follows for each quadratic non-residue class $m$ that $m=nmn/n^2=(a^2+1)c^2/n^2\equiv (ac{n}^{-1}{)}^2+(c{n}^{-1}{)}^2(\mathrm{mod}p)$ and therefore all quadratic residue classes can also be represented as the sum of two squares.