How can I prove that a sum of two integer squares, namely $ x^2 + y^2 $ (ranging from $ x = 0 \to p, \; y = 0 \to p $) is a complete system of residues (CSR) modulo $ p $ (prime)? Or, how can I prove that $ x^2 + y^2 \equiv \left \{ 0, 1, 2, \cdots, p-1 \right \} \pmod p $, for some integers $ x,y $ and all prime values of $ p $?
I've failed to prove $ \left (0, 1, 4, 9, 16, \cdots \right ) $ is a CSR modulo $ p $ , and I feel that this is an important step to solve my question.
I've also tried showing that Lagrange's four-square theorem solves the question, but it obviously gets stuck when $ x^2 + y^2 \equiv z \pmod p $, and $ z $ cannot be expressed as a sum of squares.
You should be able to show that precisely half the non-zero positive integers less than $p$ are squares modulo $p$. (This is because the polynomial $x^2 - c$ has at most $2$ roots in the field $\mathbb{Z}/p\mathbb{Z}$).
Let $n$ be the smallest integer such that $n$ is not a square modulo $p$. Then $na^2$ (modulo $p$) is also not a square modulo $p$ for $a \neq 0$, since if $na^2 = b^2$ then $n = (ba^{-1})^2$. But the minimality of $n$ tells us that $n-1 = b^2$ for some $a \neq 0$. So $na^2 = a^2 + (ba)^2$. But by counting, every non-square must be of the form $na^2$ for some $a$, and so of the form $x^2 + y^2$. And the squares are obviously of this form, so we're done.