Cardinality of set of quadratic residue of mod n.

Question

I was studying quadratic residue mod $n$, $n=p_1p_2\dots,p_k$ where $p_i$ are distinct primes such that $p_i\equiv 3\pmod4$ recently. Let $Q=\{x^2\equiv q\pmod n | gcd(q,n)=1\}$ be the set of quadratic residue mod $n$. In this case, the cardinality of $Q$ is $\frac{\phi(n)}{2^k}$. I was wondering if we drop the assumption that $gcd(q,n)=1$ and define $Q=\{x^2\equiv q\pmod n|q\in\mathbb{Z}_n-\{0\}\}$, the definition used in Wikipedia, then what will be the cardinality of $Q$? I tried finding the pattern by calculating $Q$ for some small values of $n$, but could not find any. I also used Wolfram|Aplha to find $Q$ for some larger values but there too I could not guess any relation. Any help in this direction or any suggestion for the materials or books to read on the topic will be highly appreciated.

Answer 1

I think you should be able to solve this with the Chinese Remainder Theorem. Let's start with your first case where we require $\gcd=1$. If you think about it, the Chinese Remainder Theorem it says that $$ \left(\mathbb{Z}/n\mathbb{Z}\right)^\times\cong \prod_{i=1}^k\left(\mathbb{Z}/p_i\mathbb{Z}\right)^\times $$ Now a square in $\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$ corresponds to picking a square in each $\left(\mathbb{Z}/p_i\mathbb{Z}\right)^\times$. There are $\frac{p_i-1}{2}$ such squares. So we see that the number of squares in $\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$ will be given by $$ \prod_{i=1}^k\frac{p_i-1}{2}=\frac{\phi(n)}{2^k} $$ where the above equality comes from pulling out the $k$ factors of $2$ and using the fact that $\phi(p_i)=p_i-1$ and the fact that $\phi$ is a multiplicative function. This is what you said in your question, so we now see how it is derived.

Now you are interested in the non-zero square $\mathbb{Z}/n\mathbb{Z}$ (so we drop the gcd condition). Again the Chinese Remainder Theorem tells us that $$\mathbb{Z}/n\mathbb{Z}\cong\prod_{i=1}^k\mathbb{Z}/p_i\mathbb{Z} $$ Now we will have all the squares of the above, but we will have additional squares coming from if for a prime $p_i$ the corresponding modulus is $0$. Thus, we will have for each prime $p_i$ there will be $\frac{p_i+1}{2}$ squares. Thus, we will have that the number of squares is given by $$ \prod_{i=1}^k\frac{p_i+1}{2}=\frac{\sigma(n)}{2^k} $$ But you will need to subtract $1$ from the above formula to take away $0$. I guess this might be a little less satisfying of a formula since it isn't as closed of a form. Since we don't have that $p+1$ is a multiplicative function.

Edit: From the discussion below in the comments, we should thank Erick for pointing out how we can write the product with the $\sigma$ function. Furthermore, with isnet's question about dealing with prime powers the use of the Chinese Remainder Theorem should continue to work and solving the prime power case and then combining them together. However, it should be remarked that my above computation assumes that $n$ is odd (as $2$ is always a different case). Rather than reinventing the wheel, I found this short paper by Walter D. Stangl that is fairly readable called Counting Squares in $\mathbb{Z}_n$ as this paper should address the more general case for a general modulus $n$.