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$
Context:
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$
Answer
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?
No comments:
Post a Comment