2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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}$.) $\endgroup$
    – André Nicolas
    Feb 24, 2016 at 17:09
  • $\begingroup$ 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? $\endgroup$
    – dash
    Feb 24, 2016 at 17:19
  • $\begingroup$ 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. $\endgroup$
    – André Nicolas
    Feb 24, 2016 at 17:24

1 Answer 1

Reset to default
1
$\begingroup$

Every number is congruent to either 0,1 or 2 mod 3. The only option which cubes to 1 mod 3 is 1. Therefore x must be 1 mod 3

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .