1
$\begingroup$

$a, b$ be integers, $p, q$ primes. If $x \equiv a^2 $ (mod $p$) and $x \equiv b^2$ (mod $q$), then $x \equiv c^2$ (mod $pq$) for some interger $c$.

I attempted to use Chinese Remainer Theorem, but did not get useful forms, so how to prove it?

$\endgroup$
7
  • $\begingroup$ Do you know the Legendre symbol? $\endgroup$
    – marwalix
    Jan 29 '15 at 13:49
  • 1
    $\begingroup$ You might want to specify that $p$ and $q$ are distinct primes. Otherwise $a=b=1$, $p=q=2$, and $x=3$ is a counterexample. $\endgroup$ Jan 29 '15 at 13:51
  • 1
    $\begingroup$ The Legendre is generalized into the Jacobi symbol that is multiplicative i.e $(\frac{pq}{a})=(\frac{p}{a})(\frac{q}{a})$ $\endgroup$
    – marwalix
    Jan 29 '15 at 13:57
  • 2
    $\begingroup$ @marwalix If we are working with composite numbers, not only with primes, then the name is Jacobi symbol. But even if we know that $\left(\frac{x}{pq}\right)=1$, this does not imply that $x$ is a quadratic residue modulo $pq$. $\endgroup$ Jan 29 '15 at 14:31
  • 1
    $\begingroup$ @marwalix If $\left(\frac{x}{p}\right)=\left(\frac{x}{q}\right)=-1$ then $\left(\frac{x}{pq}\right)=1$ but $x$ cannot be a perfect square modulo $pq$ because it is not a perfect square modulo $p$... $\endgroup$
    – N. S.
    Jan 29 '15 at 17:38
1
$\begingroup$

By the Chinese Remainder Theorem, there exists an element $c$ such that $$c \equiv a \pmod{p} \\ c \equiv b \pmod{q}$$

Then $$x \equiv c^2 \pmod{p}\\ x\equiv c^2 \pmod{q}$$

$\endgroup$

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.