<s>[INST] Prove that $p\mid a^2+b^2\,\Rightarrow\, p\equiv 1\pmod{\! 4}$ Let a prime number $p$ divide $a^2+b^2$ with some  $a,b \in \left\{ 1,2, \ldots , p-1 \right\}$ Prove that  $p\equiv 1 \pmod{4}$. Is the converse true?
I know that $a^2+b^2\equiv 0 \pmod{p}$ and I don't know.
 [/INST] Proof by exhaustion.
$$
p = a^2 + b^2 = 3 \pmod 4 \implies
$$
If
$$
p = 1^2 + 1^2 = 2, \\
p = 1^2 + 2^2 = 1, \\
p = 1^2 + 3^2 = 2, \\
p = 2^2 + 2^2 = 0, \\
p = 2^2 + 3^2 = 1, \\
p = 3^2 + 3^2 = 2, \\
\pmod 4
$$
Then we have a contradiciton.  By symmetry of variables $a,b$ (namely commutativity of $+$) we have covered all possibilities.
$\blacksquare$
The other proofs are impossible to understand easily.  This one is plain and simple.
</s>