# Modular equation system but not linear

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

• Well, what are the square roots of $1\pmod {19}$?
– lulu
Aug 24 at 0:35
• @lulu there are 1 and 18 Aug 24 at 0:37
• 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}$.
– lulu
Aug 24 at 0:40
• I see, thank you very much! Aug 24 at 0:44
• Another way is squaring the first 2, solving $x^2$ and sqrting . Aug 24 at 0:53

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