I have the following two equations:

$$z_1 = x_1^2 \pmod p$$ $$z_2 = x_2^2 \pmod q$$

and p and q are prime.

and I want to show $x^2$ and $z^2$ are equal mod pq

$$x^2 = x_1^2 c_1^2 + x_2^2 c^2_2$$ $$z^2 = z_1 c_1^2 + z_2 c^2_2$$

Intuitively, it seems "obvious that they are equal since $z_1 = x_1^2$ and $z_2 = x_2^2$" but these statements are only true mod p and q respectively. Then how can one claim that they are indeed equal? I guess I was wondering if I was missing some "obvious" property of modular arithmetic or/and quadratic residues?

Also for reference $c_1$ and $c_1$ are Chinese remainder theorem coefficients. i.e.

$c_1 = 1 \pmod p$

$c_1 = 0 \pmod q$

$c_2 = 0 \pmod p$

$c_2 = 1 \pmod q$


I ran into that doubt when trying to prove:

$ z \in \mathbb{QR}_{pq} \iff z \in \mathbb{QR}_p$ and $z \in \mathbb{QR}_q$


Your equations imply $x^2$ and $z^2$ are $\,\equiv z_1\pmod p,$ and $\,\equiv z_2\pmod{q},\,$ so $\,x^2\equiv z^2 \pmod{pq}\,$ by CRT. Or, directly $\,p,q\mid x^2-z^2\Rightarrow\, pq\mid x^2-z^2,\,$ since $\,p,q\,$ coprime $\Rightarrow {\rm lcm}(p,q) = pq.$

To be explicit: $\ {\rm mod}\ p\!:\ x^2 = x_1^2\color{#c00}{c_1}^{\!2}+x_2^2\color{#0a0}{c_2}^{\!2} \equiv x_1^2\equiv z_1\ $ by $\color{#c00}{c_1\equiv 1},\,\ \color{#0a0}{c_2\equiv 0}.\,$

And, similarly $\ {\rm mod}\ p\!:\ z^2 \equiv z_1 \color{#c00}{c_1}^{\!2} + z_2 \color{#0a0}{c_2}^{\!2} \equiv z_1.\ $ And similarly $\,{\rm mod}\ q.$

Remark $\ $ Essentially it concerns the uniqueness mod $pq\,$ of the solution $X$ of

$$\begin{eqnarray} X &\equiv& x_1^2\pmod p\\ X &\equiv& x_2^2 \pmod{q}\end{eqnarray}$$

This follows by CRT (the easy direction). One doesn't need to write the explicit solution given by CRT, viz. $\, X = c_1 x_1^2 + c_2 x_2^2.\,$ (Why do use $\,c_i^2$ vs. $c_i\,?)\,$ What is the context of your problem?

  • $\begingroup$ Hi Bill, ur always so helpful to my questions :). The context was that I was trying to prove the following $ z \in \mathbb{QR}_{pq} \iff z \in \mathbb{QR}_p$ and $z \in \mathbb{QR}_q$ and then ran into the doubt I pointed out. $\endgroup$ – Pinocchio Jan 20 '14 at 20:11
  • $\begingroup$ What does "viz" mean? $\endgroup$ – Pinocchio Jan 20 '14 at 20:43
  • $\begingroup$ @Pinocchio "namely", see here $\endgroup$ – Bill Dubuque Jan 20 '14 at 20:56
  • $\begingroup$ Let me tell you why I used that $c^2$.I wanted to show $x=x_1c_1+x_2c_2$ and $z=z_1c_1+z_2c_2$ satisfied $z=x^2 \pmod {pq}$.So I computed $x^2 = (x_1c_1)^2+(x_2c_2)^2 +2x_1x_2c_1c_2$.Then I applied modpq leading to: $x^2 = (x_1c_1)^2+(x_2c_2)^2 \pmod {pq}$ since the way that $c_1$ and $c_2$ is defined,means $c_1c_2$ is divisible by pq.Then I realized that if I just changed the way z was originally defined I would be very close of showing that z was indeed a quadratic residue.So I just changed the definition of it to make it look more similar to what I was looking for i.e. $z=z_1c_1^2+z_2c_2^2$ $\endgroup$ – Pinocchio Jan 20 '14 at 21:20
  • $\begingroup$ Which lead me to the exact problem I posted about, because I had the problem that $z_1 = x_1^2 \pmod p$ and $z_2 = x_2^2 \pmod q$ only applied in mod p and mod q but I had my final stuff in mod pq. Which I felt there was just something not right going on. Which lead to my post and which your answer resolved because the way that you did stuff with my "wrong" stuff made me realize that the technique you used worked on the original problem. :) $\endgroup$ – Pinocchio Jan 20 '14 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.