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