Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.