Solve simultaneous system of congruence
$$\text{$x\equiv 2\pmod{910} \qquad$ and $\qquad x\equiv 93\pmod{1001}$}$$
I tried Chinese remainder theorem on this, but it did not work. Is there a good strategy for solving simultaneous system of congruences when their modulus consist of the same multiples?
Best Answer
The first congruence means $x=910y+2$ for some $y\in\Bbb Z$. The condition on $y$ for both congruences to hold is therefore $$910y+2\equiv93\pmod{1001},$$ equivalently $$910y\equiv91\pmod{1001}.$$ As $910$, $91$ and $1001$ are all multiples of $91$, then this congruence is equivalent to $$10y\equiv1\pmod{11}$$ whose solution is $$y\equiv10\pmod{11}.$$ This means that $y=11t+10$ where $t\in\Bbb Z$. Then $$x=910(11t+10)+2=10010t+9102.$$ So the solution of the original pair of congruences is $$x\equiv9102\pmod{10010}.$$
This method solves any pair of congruences $x\equiv a\pmod m$ and $x\equiv b\pmod n$ provided these have a common solution.