# For $n=pq$, 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$.

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.

-
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

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