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.

  • 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
    Thanks Andre, worked out the proof. Shoup book is a little tough to solve on its own.2012-08-30