1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Use the Chinese Remainder Theorem. $\endgroup$ – Daniel Fischer Nov 17 '13 at 21:06
  • $\begingroup$ 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}$? $\endgroup$ – dover Nov 17 '13 at 21:14
  • $\begingroup$ You need to elaborate that a bit more when turning in, but basically it is as simple. $\endgroup$ – Daniel Fischer Nov 17 '13 at 21:16
  • $\begingroup$ I will. Thanks a lot. $\endgroup$ – dover Nov 17 '13 at 21:17
  • $\begingroup$ Silly question for Daniel: can you use CRT even if the conguences are not linear? $\endgroup$ – PITTALUGA Nov 19 '13 at 10:10
1
$\begingroup$

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$

$\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.