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.
 A: $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<r<\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.
A: Suppose  $a^2$ + $b^2$ = Mp with p  ≡ 3 (mod4). We must have by the main theorem concerning a sum of two squares the exponent of p must be even. Therefore 
$a^2$ + $b^2$ = M$p^{2n}$. On the other hand the maximum possible for $a^2$ + $b^2$ is 2${(p-1)}^2$. Hence it is deduced that M = 1 and the equality is impossible by a well known result of Fermat. 
A: Let $p|a^2+b^2$ then $a^2\equiv -b^2\pmod p$ hence by using Fermat's little theorem we have
$$
1\equiv a^{p-1}\equiv (a^2)^{(p-1/2)}\equiv (-b^2)^{(p-1/2)}\equiv (-1)^{(p-1/2)}b^{p-1}\equiv (-1)^{(p-1/2)}\pmod p
$$
Which means that $p|1-(-1)^{(p-1/2)}$, so $p\equiv 1\pmod 4$.
A: 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.
