Let's consider equation $s^2 \equiv-1(mod \;p)$. Theorem says:
For $p = 4m+1$ equation $s^2 \equiv-1(mod \;p)$ has two solutions $s \in \{1,2,...,p-1\}$
For $p = 2$ equation $s^2 \equiv-1(mod \;p)$ has one solution $p =2$
For $p = 4m+3$ equation $s^2 \equiv-1(mod \;p)$ has no solutions
Proof
For odd $p$ let's put equivalance relation which identifies element with it's inverse and opposite elment on $\mathbb{Z}_p$.
It means that we have equivalence class in form of:
$$\{x, -x, \bar{x}, -\bar{x}\}$$
But it can be shorten. Let's consider these three cases:
(1) $x \equiv -x$ - it cannot be satisfied, because $p$ is odd
(2) $x \equiv \bar{x} \Leftrightarrow x^2 \equiv 1 \Leftrightarrow x =1 \lor x = p-1$. It means that equivalence class is a set $\{1, p-1\}$
(3) $x \equiv -\bar{x} \Leftrightarrow x^2 \equiv -1 $
This equation can have no solutions or two different ones: $x_0$ and $p-x_0$. When it does, the equivalence class is in form of $\{x_0, p - x_0\}$.
Set $\{1,2,...,p-1\}$ has $p-1$ elements and we divided it into four-element equivalence classes (or two-element - according to above).
Now if $p-1=4m+2$ then we have only one couple $\{1, p-1\}$ and the rest of the classes is four-element.
Due to this fact equation $s^2 \equiv-1(\mod \;p)$ has no solutions. $(*)$
But if we take $p - 1 \equiv 4m$ then we have also additional two-element equivalence class containing solutions of $s^2 \equiv-1(mod \;p)$ which we were looking for. $(**)$
Question section
I have a question related to this proof - I marked by $(*), (**)$ parts in proof to which I have queries. How exactly using this facts from contents of equivalence classes we can justify something on solutions of equation $s^2 \equiv -1 (mod \; p)$ ? I just don't quite get it. Could you please give me a hand explaining this part of the proof ?
EDIT The remaining thing for me two understand is only that:
(1) For $p-1 = 4m+2$ there is only one two-element equivalence class $\{1, p-1\}$ and other are four-element.
(2) For $p - 1 = 4m$ there is one equivalence class $\{x_0, p-x_0\}$, one $\{1, p-1\}$ and remaining ones are four-element.
Maybe it's obvious but I don't understand how it can be truth. For example equivalent formulation of (1) is that:
$\exists! x_0 : x_0 \equiv \bar{x_0} (mod \; 4m+2)$ and for remaining $x \in \{1,2,...,4m+2\} \setminus \{x_0\}$ we have that equivalence class cannot be shorten. Could you please explain to me how to prove that ?
If $s^2\equiv-1\pmod p$, then $s\equiv\bar ss^2\equiv\bar s(-1)\equiv-\bar s\pmod p$ and hence also $-s\equiv\bar s\pmod p$, so the equivalence class $\{s,-s,\bar s,-\bar s\}$ actually has only two members, $s$ and $-s$. Thus, in order for $x^2\equiv-1\pmod p$ to have a solution, there must be a two-element equivalence class, and it can’t be the class $\{1,p-1\}$, because neither $1$ nor $p-1$ is a solution to $x^2\equiv-1\pmod p$.
When $p-1=4m+2$, $\{1,p-1\}$ is the only two-element equivalence class, so $x^2\equiv-1\pmod p$ has no solution.
When $p-1=4m$, however, there must be a two-element equivalence class $\{x_0,p-x_0\}$ that is not the class $\{1,p-1\}$. (This is because if $\{1,p-1\}$ were the only two-element equivalence class, and all of the other equivalence classes had $4$ elements, we’d have $p-1=4m+2$, where $m$ is the number of four-element classes.) Now the members of the equivalence class of $x_0$ are $x_0,-x_0,\overline{x_0}$, and $-\overline{x_0}$, and $-x_0$ is $p-x_0$ modulo $p$, so $\overline{x_0}$ must be one of $x_0$ and $p-x_0$. We know that $x_0$ isn’t $1$ or $1-p$, so $x_0^2\not\equiv1\pmod p$, and therefore $\overline{x_0}\ne x_0$. This means that $\overline{x_0}=p-x_0\equiv-x_0\pmod p$, so
$$1\equiv x_0\overline{x_0}\equiv x_0(-x_0)\equiv -x_0^2\pmod p\,,$$
and therefore $x_0^2\equiv-1\pmod p$.