Number of quadratic residues mod n.

**RaisinBread** · November 23rd 2011, 05:26 PM

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...

**RaisinBread** · November 25th 2011, 08:14 AM

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.

Thread: Number of quadratic residues mod n.

LinkBack

Thread Tools

Display

Number of quadratic residues mod n.

Re: Number of quadratic residues mod n.

Similar Math Help Forum Discussions

Quadratic Residues

Quadratic residues

Quadratic Residues

Sum of quadratic residues

quadratic residues

Search Tags