Prove that $p\mid a^2+b^2\,\Rightarrow\, p\equiv 1\pmod{\! 4}$ [duplicate]

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.

Solution 1:

$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.

Solution 2:

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.

Solution 3:

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$.