# CRT - non-linear system of equations

I don't know how to solve system of equations using CRT when there is some quadratic/cubic variable. For example:

System 1: $$\boxed{x^3 \equiv 1 \pmod{3}}$$ $$12x \equiv 9 \pmod{15}$$

System 2: $$3x \equiv 6 \pmod{9}$$ $$\boxed{x^2 \equiv 1 \pmod{4}}$$ $$4x \equiv 2 \pmod{5}$$

I think (please correct me if I'm wrong) the quadratic equation from System 2 can be rewritten into linear equations as $$x \equiv \pm 1 \pmod{2}$$.

How can I rewrite the cubic equation from System 1 into linear equations to be able to use CRT?

• The cubic is equivalent to the linear congruence $x\equiv 1\pmod{3}$. The quadratic in the second list has no solution. (I am assuming you really mean $x^2\equiv 2\pmod{4}$.) Feb 24, 2016 at 17:09
• I edited the question, there was an error in the System 2. Why do we need to change modulo from 4 to 2 in System 2?
– dash
Feb 24, 2016 at 17:19
• We don't have to, but it saves time. the solutions to $x^2\equiv 1\pmod{4}$ are $x\equiv \pm 1\pmod{4}$. So if we stick to $4$ we will have to solve two systems of congruences. However, if we collapse $x^2\equiv \pm 1\pmod{4}$ to the equivalent $x\equiv 1\pmod{2}$, there is only one system of congruences to solve. Feb 24, 2016 at 17:24