Partition on $Z_p$ I'm trying to understand what is established in Proofs from the Book (from Eigner and Ziegler) concerning the representation of numbers as a sum of two squares.
Consider $\mathbb{Z}_p$, $p$ an odd prime. At first, the authors affirm that is always possible to partition $\{1,2, \dots, p-1\}$ in quadruples $\{x, -x, \overline{x}, - \overline{x}\}$, where $-x$ is the additive inverse of $x$ and $\overline{x}$ is the multiplicative inverse of $x$. If two of these numbers are equal, the class reduces to a pair of elements. I proved the last affirmation.
My doubt is: the authors affirm that, if $p-1=4m+2$ we will have just one pair and the other elements will be quadruples and, if $p-1=4m$, there will be 2 pairs. According to the number of these pairs, they establish the number of solutions of $x^2 \equiv 1 \mod p$.
All my examples indicates that it is true (of course it is because the book is a classic!), but I can't understand it.
 A: If $p-1 = 4m+2$ for some $m$, then the number of pairs must be odd.  (Otherwise, after taking the union of all quadruples and pairs, we’d get a total number of elements that was divisible by $4$.)
Similarly, if $p−1=4m$, then the number of pairs must be even.  Thus, to prove the authors’ claim, it suffices to prove that there are at most two pairs, regardless of the value of $p-1$ modulo $4$.
The key to proving that there are at most two pairs is the fact that if $p$ is prime, then a degree $n$ polynomial can have at most $n$ roots modulo $p$.  This can be proved via induction. (See, e.g. If $f$ is a polynomial of degree $n$, then $f(x) \equiv 0\pmod p$ has at most $n$ solutions.).  Here, the relevant polynomials are $f(x) = x^2 -1$ and $g(x) = x^2+1$, because a quadruple $\{x,-x, \overline{x}, - \overline{x} \}$ reduces to a pair if and only if $x$ and $-x$ are both roots of $f$ or they are both roots of $g$.
 You probably proved something like this in the course of proving that if two elements of $\{x,-x, \overline{x}, - \overline{x} \}$ are equal, then it reduces to a pair; however, I’ve appended a proof for the sake of completeness.*  
Since $f$ and $g$ each have at most $2$ roots mod $p$, at most one quadruple can be reduced to a pair by way of solving each of $f$ and $g$.  Thus, at most two quadruples can be reduced to pairs.
We note that $f$ always has two solutions mod $p$, namely $1$ and $p-1$.  Thus, the one pair we get when $p = 4m+1$ must result from roots of $f$, not roots of $g$. (The roots of $f$ and $g$ never coincide assuming that $p$ is odd.)

*Appendix: Proof that $\{x,-x, \overline{x}, - \overline{x} \}$ reduces to a pair if and only if $x$ and $-x$ solve $f$ or $x$ and $-x$ solve $g$.
By setting pairs from $\{x,-x, \overline{x}, - \overline{x} \}$ equal, one obtains six equations:
$$
x = -x \tag{1};
$$
$$
x = \overline{x}; \tag{2}
$$
$$
x = - \overline{x}; \tag{3}
$$
$$
-x = \overline{x}; \tag{4}
$$
$$
 -x = - \overline{x}; \tag{5}
$$
$$
\overline{x} = -\overline{x}. \tag{6}
$$
However, (1) and (6) are impossible for an odd $p$, while (2) is equivalent to (5) and (3) is equivalent to (4).  Thus, the quadruple reduces to a pair if and only if (2) is satisfied or (3) is satisfied.  In turn, (2) is satisfied if and only if $x$ and $-x$ are both roots of $f$, whereas (3) is satisfied if and only if $x$ and $-x$ are roots of $g$.  
