Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Hint: When is a number a square mod $pq$? – Thomas Andrews Aug 30 '12 at 15:11
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
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|cite|improve this answer
How did you arrive at this result? – Abhishek Anand Aug 30 '12 at 16:09
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
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

Your Answer


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.