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.
$1)$ $\ \,a^2\equiv -b^2\,\Leftrightarrow\, (a/b)^2\equiv -1\,\Rightarrow\, (a/b)^4\equiv 1\pmod{\!p}$, so $\text{ord}_p (a/b)=4$.   

Fermat's little (FLT) $(a/b)^{p-1}\equiv 1\pmod{\!p}$ implies $4\mid p-1$ (proof below).    

Theorem: $a^k\equiv 1\pmod{\!p}\,\Rightarrow\, \text{ord}_p a\mid k$.   

Proof: If not, then $\,k=m\left(\text{ord}_pa\right)+r\,$ with $\,0&lt;r&lt;\text{ord}_p a$    

But then $a^k\equiv (a^{\text{ord}_pa})^m(a^r)\equiv 1^ma^r\equiv a^r\equiv 1\pmod {\!p}$ - contradiction.

$2)\ $ By contradiction: if $\, p\equiv 3\pmod{\! 4}$,$\,$ then $\, a^2\equiv -b^2\,\Rightarrow\, (a/b)^2\equiv -1\,\stackrel{(p-1)/2}\Rightarrow$   

$ (a/b)^{p-1}\equiv \color{#00F}{(-1)^{(p-1)/2}}\equiv \color{#00F}{-1}\, $ mod $p\,$ contradicts FLT.
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.