Results 1 to 2 of 2

Thread: 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 $\displaystyle n$ for any $\displaystyle 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 - $\displaystyle n$ is a prime number. In this case, I have already proved that there are $\displaystyle \frac{(n-1)}{2}$ quadratic residues.

    2 - $\displaystyle n$ is composite.
    2.1 - $\displaystyle n$ has a primitive root. In this case, there are $\displaystyle \frac{\phi(n)}{2}$ quadratic residues.
    2.2 - $\displaystyle 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 $\displaystyle n=p_1^{e_1}\cdot ... \cdot p_k^{e_k}$ to be the prime factorization of $\displaystyle n$, and thus, a number $\displaystyle b$ is a primitive root mod $\displaystyle n$ if and only if there exists $\displaystyle x$ such that

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

    $\displaystyle x^2\equiv b ~ ~ ~ mod ~ p_1^{e_1}$
    $\displaystyle x^2\equiv b ~ ~ ~ mod ~ p_2^{e_2}$
    ...
    $\displaystyle 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; Nov 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 $\displaystyle n$ has a primitive root, then there are $\displaystyle \phi{(n)}/2$ solutions if $\displaystyle \phi{(n)}$ is even and $\displaystyle (\phi{(n)}-1)/2$ is $\displaystyle \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: Feb 17th 2009, 04:13 PM
  3. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 3rd 2008, 07:15 PM
  4. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 27th 2008, 06:45 PM
  5. quadratic residues
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Sep 13th 2006, 11:34 AM

Search Tags


/mathhelpforum @mathhelpforum