1. Assume p to be an odd prime and a is any integer not congruent to 0 modulo p. It can be proven that the congruence (x^2) __=__ ((-a)^2)(mod p) has solutions IFF p __=__ 1 (mod 4).

How is that proven?

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} \).