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

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