Results 1 to 2 of 2

Math Help - quadratic nonresidues and residues

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    14

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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)
    Last edited by PaulRS; January 13th 2010 at 08:06 AM. Reason: Correction
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Amount of quadratic residues and nonresidues modulo p
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 23rd 2011, 09:47 PM
  2. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 11th 2011, 10:05 PM
  3. Quadratic Residues
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: July 17th 2009, 08:26 PM
  4. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 4th 2009, 02:19 PM
  5. quadratic residues
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 13th 2006, 11:34 AM

Search Tags


/mathhelpforum @mathhelpforum