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 for any using the Chinese Remainder Theorem. Chinese remainder theorem - Wikipedia, the free encyclopedia
So far, I have tried dividing the question in distinct cases;
1 - is a prime number. In this case, I have already proved that there are quadratic residues.
2 - is composite.
2.1 - has a primitive root. In this case, there are quadratic residues.
2.2 - 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 to be the prime factorization of , and thus, a number is a primitive root mod if and only if there exists such that
which is true if and only if
However, from there, I have no idea how I could count the quadratic residues mod n...
Re: Number of quadratic residues mod n.
Hm, just realized I made a little mistake for case 2.1, if has a primitive root, then there are solutions if is even and is is odd.