3
$\begingroup$

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.

  • 2
    Hint: When is a number a square mod $pq$?2012-08-30
  • 0
    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$?2012-08-30

1 Answers 1

2

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

  • 0
    How did you arrive at this result?2012-08-30
  • 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.2012-08-30
  • 0
    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?2012-08-30
  • 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$.2012-08-30
  • 0
    Thanks Andre, worked out the proof. Shoup book is a little tough to solve on its own.2012-08-30