If $p,q$ distinct primes with $p,q \equiv 1 \bmod 4$, show that $x^2 \equiv -1 \pmod {pq}$ is solveable

I can't seem to get anywhere with this problem. Any hints would be much appreciated:

Suppose that $p$ and $q$ are distinct primes satisfying $p, q \equiv 1 \bmod{4}$. Show that the congruence $x^2 \equiv -1 \bmod {pq}$ has a solution.

• Use the Chinese Remainder Theorem. – Daniel Fischer Nov 17 '13 at 21:06
• Oh man. So it's as simple as saying: We have that there is an $x_1$ and a $x_2$ such that $x_1 \equiv (-1)^{1/2} \bmod {p}$ and $x_2 \equiv (-1)^{1/2} \bmod {q}$, so by the CRT we have that there is an $x$ such that $x \equiv (-1)^{1/2} \bmod {pq}$? – dover Nov 17 '13 at 21:14
• You need to elaborate that a bit more when turning in, but basically it is as simple. – Daniel Fischer Nov 17 '13 at 21:16
• I will. Thanks a lot. – dover Nov 17 '13 at 21:17
• Silly question for Daniel: can you use CRT even if the conguences are not linear? – PITTALUGA Nov 19 '13 at 10:10

By supplemental laws of quadratic reciprocity, we know that $-1$ is a square mod $p$ exactly when $p \equiv 1 \pmod 4$. So we know there exist $x_p$ such that $x_p^2 \equiv -1 \pmod p$ and $x_q$ such that $x_q^2 \equiv -1 \pmod q$.
By the Chinese Remainder Theorem, there is a solution $x$ to the system of congruences \begin{align} x &\equiv x_p \pmod p \\ x &\equiv x_q \pmod q \end{align} and that this $x$ is defined $\bmod {pq}$. Since $x^2 \equiv -1$ both $\bmod p$ and $\bmod q$, this $x$ is the solution you're looking for. $\diamondsuit$