quadratic nonresidues and residues

**ilikecandy** · January 12th 2010, 07:28 PM

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?

**PaulRS** · January 13th 2010, 04:17 AM

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)$

Thread: quadratic nonresidues and residues

LinkBack

Thread Tools

Display

quadratic nonresidues and residues

Similar Math Help Forum Discussions

Amount of quadratic residues and nonresidues modulo p

Sum of quadratic residues

Quadratic Residues

Quadratic residues

quadratic residues

Search Tags