0
$\begingroup$

I'm trying to solve this system of equations and have used the Chinese remainder theorem with the first two equations, but I don't know how to deal with the quadratic term.

\begin{array}{rcl} x &\equiv 2 \pmod{5} \\ 3x &\equiv -4 \pmod{11} \\ x^2 &\equiv 1 \pmod{19} \end{array}

$\endgroup$
5
  • 3
    $\begingroup$ Well, what are the square roots of $1\pmod {19}$? $\endgroup$
    – lulu
    Aug 24 at 0:35
  • $\begingroup$ @lulu there are 1 and 18 $\endgroup$
    – Fermatto
    Aug 24 at 0:37
  • $\begingroup$ Good, so now set up two systems of simultaneous congruences. In both use the top two of your three. Then add $x\equiv \pm 1\pmod {19}$. You should get two different residue classes $\pmod {5\times 11\times 19}$. $\endgroup$
    – lulu
    Aug 24 at 0:40
  • $\begingroup$ I see, thank you very much! $\endgroup$
    – Fermatto
    Aug 24 at 0:44
  • $\begingroup$ Another way is squaring the first 2, solving $x^2$ and sqrting . $\endgroup$ Aug 24 at 0:53
0
$\begingroup$

Note that we have \begin{align*} x^2 &\equiv 1 \pmod{19}\\ x^2 - 1 &\equiv 0 \pmod{19}\\ (x - 1)(x + 1) &\equiv 0 \pmod{19}\\ x &\equiv \pm 1 \pmod{19} \end{align*} Thus we have reduced the quadratic condition to a linear condition, and thus can use Chinese Remainder Theorem. We have \begin{align*} 3x &\equiv -4 \pmod{11}\\ x &\equiv 6 \pmod{11} \end{align*} Solving these, we have \begin{align*} x &\equiv 2 \pmod{5}\\ x &\equiv 6 \pmod{11}\\ x &\equiv \pm 1 \pmod{19}\\ \implies x &\equiv 457, 512 \pmod{1045} \end{align*}

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