Results 1 to 2 of 2

Math Help - Number of quadratic residues mod n.

  1. #1
    Junior Member RaisinBread's Avatar
    Joined
    Mar 2011
    Posts
    37

    Number of quadratic residues mod n.

    Hey, I'm having trouble with the following;

    I'm trying to find a formula for the amount of quadratic residues mod n for any n\in \mathbb{N} using the Chinese Remainder Theorem. Chinese remainder theorem - Wikipedia, the free encyclopedia

    So far, I have tried dividing the question in distinct cases;

    1 - n is a prime number. In this case, I have already proved that there are \frac{(n-1)}{2} quadratic residues.

    2 - n is composite.
    2.1 - n has a primitive root. In this case, there are \frac{\phi(n)}{2} quadratic residues.
    2.2 - n does not have a primitive root. Now this is the case I'm having trouble with. My only guess, since I have to use the Chinese Remainder Theorem, is that I could define n=p_1^{e_1}\cdot ... \cdot p_k^{e_k} to be the prime factorization of n, and thus, a number b is a primitive root mod n if and only if there exists x such that

    x^2\equiv b ~ ~ ~ mod ~ n
    which is true if and only if

    x^2\equiv b ~ ~ ~  mod ~ p_1^{e_1}
    x^2\equiv b ~ ~ ~  mod ~ p_2^{e_2}
    ...
    x^2\equiv b ~ ~ ~  mod ~ p_k^{e_k}

    However, from there, I have no idea how I could count the quadratic residues mod n...
    Last edited by RaisinBread; November 23rd 2011 at 06:29 PM. Reason: Messing up latex
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member RaisinBread's Avatar
    Joined
    Mar 2011
    Posts
    37

    Re: Number of quadratic residues mod n.

    Hm, just realized I made a little mistake for case 2.1, if n has a primitive root, then there are \phi{(n)}/2 solutions if \phi{(n)} is even and (\phi{(n)}-1)/2 is \phi{(n)} is odd.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 12th 2009, 09:42 AM
  2. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 17th 2009, 04:13 PM
  3. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2008, 07:15 PM
  4. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 06:45 PM
  5. quadratic residues
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 13th 2006, 11:34 AM

Search Tags


/mathhelpforum @mathhelpforum