Help needed in understanding proof: Every odd prime $p$ has exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues.
We assume there exist $k$ incongruent quadratic residues and each yield two solutions of the equation $x^2 \equiv a (\mod p)$. Also each of these solutions are incongruent, right ? So we have $2k$ solutions to quadratic congruences.
Then there are $p-1$ squares of the least residues, $1$ through $p-1$. But these need not be incongruent (consider $p = 7$ and $1^2, 6^2$). Then $2k = p-1$, why ?
Could someone explain to me in details what the reasoning is ?
Best Answer
If a nonzero number $y$ is a square modulo $p>2$, say $=x^2$, then it is also $=(-x)^2$. But $x=-x=\mod p\iff p\mid 2x\iff p\mid x$ since $p$ is odd, so these numbers are distinct. Moreover, since $\Bbb Z_p$ is a field, $x^2=y$ has at most two solutions, hence none or exactly two by the above. It follows that if $k$ is the number of quadratic residues, there are $2k$ noncongruent elements in $\Bbb Z_p$. Thus, $k\leqslant \dfrac{p-1}2$.
Consider now the $p-1$ numbers $1,2,\ldots,\frac{p-1}2,-\frac{p-1}2,\ldots,-2,-1$. These are all the nonzero classes modulo $p$, and squaring them gives $\frac{p-1}2$ squares. Thus $k\geqslant \dfrac{p-1}2$.