Why has the interval changed from p-1 to p/2?

Question

I know that there are $(p-1)/2$ quadratic residues in $Z_{p}^{\times} $. However, I am unsure how this means that the interval p-1 changes to p/2?

Answer 1

The first $S_p$ is the set of $a$s in $[1,p-1]$. The second is the set of $a$s and $p-a$s with $a$ in $[1,p/2)$. The line before, "if $a$ is a quadratic residue, so is $p-a$" means you can pair up the elements of the first $S_p$, which is what the second $S_p$ is doing.

I submit that the "$\{a,p-a : \dots$" notation is a little weird.

Example: $13 \cong 1 \pmod{4}$. The quadratic residues modulo $13$ are $1$, $3$, $4$, $9$, $10$, and $12$. We can gather these into $S_p$ as : \begin{align*} \{a &: a \in [1,p-1]\} &: &\{1,3,4,9,10,12\} \\ \{a, p-a &: a \in [1,p-1]\} &: &\{1,12,\ 3,10,\ 4,9,\ 9,4,\ 10,3,\ 12,1\} = \{1,3,4,9,10,12\}\\ \{a, p-a &: a \in [1,p/2]\} &: &\{1,12,3,10,4,9\} = \{1,3,4,9,10,12\}\\ \end{align*}