# quadratic nonresidues and residues

Printable View

• January 12th 2010, 07:28 PM
ilikecandy
quadratic nonresidues and residues
How can I show that the number of quadratic residues modulo m is equal to the number of quadratic nonresidues modulo m in the set of reduced residue system modulo m?
• January 13th 2010, 04:17 AM
PaulRS
Note that $1^2\equiv (p-1)^2(\bmod.p)$, $2^2\equiv (p-2)^2(\bmod.p)$, ...
So that the only distinct quadratic residues are: $1^2(\bmod.p)...\left(\tfrac{p-1}{2}\right)^2(\bmod.p)$, but we have $p-1=|\mathbb{Z}_p^{\times}|$ hence the rest of them must be non-quadratic residues, that is we have $\tfrac{p-1}{2}$ quadratic residues and $\tfrac{p-1}{2}$ non-quadratic residues.

EDIT: Thought I'd clarify a bit: $x^2\equiv{y^2}(\bmod.p)$ if and only if $(x-y)\cdot (x+y)\equiv{0}(\bmod.p)$ since p is prime either $x \equiv{y}(\bmod.p)$ or $x \equiv{p-y}(\bmod.p)$