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.

For $n=pq$, where p,q are distinct odd primes show that there exist $\alpha, \beta \in Z_n^*$ such that $\alpha, \beta \notin (Z_n^*)^2$ and $\alpha \cdot \beta \notin (Z_n^*)^2$.
Here if we try to use Chinese Remainder theorem results then let :
$$\alpha \equiv \alpha_p\mod p\,\,,\qquad\alpha \equiv \alpha_q\mod q$$
$$\beta \equiv \beta_p\mod p\,\,,\qquad\beta \equiv \beta_q\mod q$$
Since $\alpha \notin (Z_n^*)^2$, what can we say about $\alpha_p$ and $\alpha_q$? Do $\alpha_p \notin (Z_p^*)^2$ and $\alpha_q \notin (Z_q^*)^2$ also hold? Is there another approach to solve this problem?

PS: Couldn't insert "p,q are distinct primes" in title due length restriction.

share|improve this question
2  
Hint: When is a number a square mod $pq$? –  Thomas Andrews Aug 30 '12 at 15:11
    
I replaced your \dot with \cdot. You could also do without a dot altogether, as multiplication is then assumed by default. –  Jyrki Lahtonen Aug 30 '12 at 15:17
    
Thomas, are you referring to the result that if $\alpha \in (Z_{pq}^*)^2$ then $\alpha \in (Z_p^*)^2$ and $\alpha \in (Z_q^*)^2$? –  Abhishek Anand Aug 30 '12 at 15:43
add comment

1 Answer 1

up vote 1 down vote accepted

Hint: Let $\alpha_p$ be a non-square modulo $p$ (quadratic non-residue of $p$). Then there exists $\alpha$ such that $\alpha\equiv \alpha_p\pmod{p}$ and $\alpha\equiv 1\pmod{q}$. Produce $\beta$ in an analogous way.

Added: Then $\alpha\beta\equiv \alpha_p \pmod{p}$ and $\alpha\beta\equiv \beta_q\pmod{q}$.

Now we need to show that none of $\alpha$, $\beta$, or $\alpha\beta$ is a square modulo $pq$.

share|improve this answer
    
How did you arrive at this result? –  Abhishek Anand Aug 30 '12 at 16:09
1  
Chinese Remainder Theorem if you are in number theory. Fact that $\mathbb{Z}_{pq}^\ast$ is the direct product of $\mathbb{Z}_p^\ast$ and $\mathbb{Z}_q^\ast$ if you are more group-theory oriented. –  André Nicolas Aug 30 '12 at 16:11
    
So what does it say about $\alpha$, having a quadratic non-residue in p and quadratic residue of 1 in q? My understanding of CRT is a little bit sketchy. Does it imply $\alpha$ is a quadratic non-residue of pq? –  Abhishek Anand Aug 30 '12 at 16:32
1  
Yes. If $x^2\equiv \alpha \pmod{pq}$, then $x^2\equiv \alpha\pmod{p}$. But $\alpha\equiv \alpha_p\pmod{p}$, so $x^2\equiv \alpha_p\pmod{p}$, contradicting the fact that $\alpha_p$ is a quadratic non-residue of $p$. –  André Nicolas Aug 30 '12 at 16:37
    
Thanks Andre, worked out the proof. Shoup book is a little tough to solve on its own. –  Abhishek Anand Aug 30 '12 at 16:55
add comment

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.