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?

Printable View

- January 12th 2010, 07:28 PMilikecandyquadratic 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 AMPaulRS
Note that , , ...

So that the only distinct quadratic residues are: , but we have hence the rest of them must be non-quadratic residues, that is we have quadratic residues and non-quadratic residues.

EDIT: Thought I'd clarify a bit: if and only if since p is prime either or