Results 1 to 2 of 2

Thread: 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 $\displaystyle 1^2\equiv (p-1)^2(\bmod.p)$, $\displaystyle 2^2\equiv (p-2)^2(\bmod.p)$, ...
    So that the only distinct quadratic residues are: $\displaystyle 1^2(\bmod.p)...\left(\tfrac{p-1}{2}\right)^2(\bmod.p)$, but we have $\displaystyle p-1=|\mathbb{Z}_p^{\times}|$ hence the rest of them must be non-quadratic residues, that is we have $\displaystyle \tfrac{p-1}{2}$ quadratic residues and $\displaystyle \tfrac{p-1}{2}$ non-quadratic residues.

    EDIT: Thought I'd clarify a bit: $\displaystyle x^2\equiv{y^2}(\bmod.p)$ if and only if $\displaystyle (x-y)\cdot (x+y)\equiv{0}(\bmod.p)$ since p is prime either $\displaystyle x \equiv{y}(\bmod.p)$ or $\displaystyle x \equiv{p-y}(\bmod.p)$
    Last edited by PaulRS; Jan 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: Jul 23rd 2011, 09:47 PM
  2. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Feb 11th 2011, 10:05 PM
  3. Quadratic Residues
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: Jul 17th 2009, 08:26 PM
  4. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 4th 2009, 02:19 PM
  5. quadratic residues
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Sep 13th 2006, 11:34 AM

Search Tags


/mathhelpforum @mathhelpforum