# Number of roots for quadratic residues

Let $n \in Z$ and define $QR_n=\{x \in Z_n|\exists y \in Z_n :y^2=x (mod\ n)\}$.

How can I show that $\forall x \in QR_n$ it hold that $|\{ y \in Z_n:y^2=x (mod\ n)\}|=\frac{n}{|QR_n|}$ ?

Why am I intersted in such result? I want to be able to say that if I choose $x \sim U(Z_n)$ then it hold that $x^2 \sim U(QR_n)$ (I am looking for a way to uniformly choose element in $QR_n$ without computing all the elements in $QR_n$ - a computer science problem...)

Thanks.

-

EDIT: Actually I assume by $Z_n$ you mean the multiplicative group of integers mod $n$.

By the Chinese remainder theorem it suffices to show that your statement holds for powers of primes.

If $n=p^m$ for $p$ an odd prime, then $\mathbb{Z}_n$ is cyclic and has a primitive root $z$. It follows that $z^{2\log y}\equiv z^{\log x}\pmod n$ whenever $2\log y\equiv \log x \pmod {\phi(n)}$, so all QRs of $\mathbb{Z}_n$ have exactly two square roots.

For $n=2,4$ we can check the statement directly. For $n=2^m$ for $m>2$, we know that $x$ is a QR if and only if $x\equiv 1 \pmod 8$, so $|QR(n)| = |\mathbb{Z}_n|/4$. Moreover, if $x$ has a square root $y\in\mathbb{Z_{2^m}}$, it has at least four, of the form $$\pm y + 2^{m-1}k, \qquad k\in\{0,1\},$$ so every QR has exactly four square roots.

-
Does "primitive root" means "generator"? –  zvisofer Feb 25 '13 at 22:13
@zvisofer Yes, it does. –  user7530 Feb 25 '13 at 22:18
"so all QRs of $Z_n$ have exactly two square roots." I am intersted in DISTINCT roots. How is that statement true for an odd $n$? if there are $x$ distinct QRs in $Z_n$ there are $2x$ distinct roots for these QRs, but this equals to the total numbers of elements in $Z_n$, ie equal to $n$. But $n \neq 2x$ because $n$ is odd. –  zvisofer Feb 26 '13 at 14:29
@zvisofer I don't understand the question. The roots are distinct because, e.g., the only solution to $x = -x$ modulo an odd integer is $x=0$, and $0$ is never in $\mathbb{Z}_n$. –  user7530 Feb 26 '13 at 15:32