2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ To summarize Steven Creech's answer, this can be written as $\sigma(n)/2^k - 1$. $\endgroup$
    – Erick Wong
    Aug 10, 2023 at 20:23
  • $\begingroup$ It seems there's no natural reason in this context to assume that $p_i\equiv3$ (mod $4$); being odd is enough. $\endgroup$ Aug 11, 2023 at 5:05

1 Answer 1

5
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Since this is the squarefree case, it happens that $\prod (p+1)$ can be identified with the sum of divisors function $\sigma(n)$, though this isn't true in general. $\endgroup$
    – Erick Wong
    Aug 10, 2023 at 19:30
  • $\begingroup$ Good catch, so the general formula for square-free should be $\frac{\sigma(n)}{2^k}-1$ $\endgroup$ Aug 10, 2023 at 21:39
  • $\begingroup$ What if $p_i$ are not distinct? For example, lets say $n=p^3$. $\endgroup$
    – isnet
    Aug 11, 2023 at 6:37
  • $\begingroup$ I added an edit that links to a paper that I think will answer your question in general $\endgroup$ Aug 11, 2023 at 14:18
  • $\begingroup$ Thanks for the suggested paper. $\endgroup$
    – isnet
    Aug 14, 2023 at 12:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .