Originally Posted by

**chiph588@** Now for the other direction:

-------

**Lemma:** Given $\displaystyle (a,p)=1 $, suppose $\displaystyle n $ is the smallest number greater than $\displaystyle 0 $ such that $\displaystyle a^n\equiv1\bmod{p} $ and $\displaystyle a^m\equiv1\bmod{p} $ where $\displaystyle m>n $, then $\displaystyle n\mid m $.

**Proof:** By the division algorithm, $\displaystyle m=qn+d $ where $\displaystyle 0\leq d <n $. So we then get $\displaystyle 1\equiv a^m=a^{qn+d}=\left(a^n\right)^q\cdot a^d \equiv 1\cdot a^d=a^d\bmod{p} $. Since $\displaystyle d<n $ and $\displaystyle a^d\equiv1\bmod{p} $, by the minimality of $\displaystyle n $ this forces $\displaystyle d=0 $. So we see that $\displaystyle m=qn\implies n\mid m $.

-------

Suppose $\displaystyle x^2\equiv-a^2\bmod{p} $ is solvable. This implies $\displaystyle \left(a^2\right)^{-1}\cdot x^2=\left(xa^{-1}\right)^2\equiv-1\bmod{p}\implies y^2\equiv-1\bmod{p} $ is solvable. So observe that it's equivalent to show $\displaystyle x^2\equiv-1\bmod{p} $ solvable implies $\displaystyle p\equiv1\bmod{4} $.

Since $\displaystyle p $ is odd, $\displaystyle x\neq1 $, so we have the following:

$\displaystyle x^1\not\equiv1\bmod{p} $

$\displaystyle x^2\equiv-1\not\equiv1\bmod{p} $

$\displaystyle x^3\equiv(-1)x\not\equiv1\bmod{p} $

$\displaystyle x^4\equiv(-1)^2\equiv1\bmod{p} $

So as you can see, $\displaystyle 4 $ is the smallest exponent greater than $\displaystyle 0 $ such that $\displaystyle x^n\equiv 1\bmod{p} $. Now by Fermat's little theorem, since $\displaystyle (x,p)=1\implies x^{p-1}\equiv1\bmod{p} $. By our above Lemma, this implies $\displaystyle 4\mid p-1 \implies p\equiv1\bmod{4} $.