# If $x$ is a square modulo two primes, then it is a square modulo their product

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

• Do you know the Legendre symbol? Jan 29 '15 at 13:49
• 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. Jan 29 '15 at 13:51
• The Legendre is generalized into the Jacobi symbol that is multiplicative i.e $(\frac{pq}{a})=(\frac{p}{a})(\frac{q}{a})$ Jan 29 '15 at 13:57
• @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$. Jan 29 '15 at 14:31
• @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$... Jan 29 '15 at 17:38

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