Solve simultaneous system of congruence $x\equiv 2\pmod{910}$ and $x\equiv 93\pmod{1001}$

Question

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?

Answer 1

$910 = 2 \times 5 \times 7 \times 13$ and $1001 = 7 \times 11 \times 13$. Therefore, from the first statement we have:

$$x \equiv 0 \pmod 2, \ \ 2 \pmod 5, \ \ 2 \pmod 7, \ \ 2 \pmod {13}$$

and from the second statement we have: $$x \equiv 2 \pmod {7}, \ \ 5 \pmod {11}, \ \ 2 \pmod {13}$$

so now you can use the Chinese remainder theorem on:

$$x \equiv 0 \pmod 2$$ $$x \equiv 2 \pmod 5$$ $$x \equiv 2 \pmod 7$$ $$x \equiv 5 \pmod {11}$$ $$x \equiv 2 \pmod {13}$$

Answer 2

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.

Answer 3

$\!\begin{align}{\rm Notice}\quad\ \, \color{#c00}{1001}-\color{#0a0}{910} &\,=\, \color{#c00}{93} - \color{#0a0}2\\[.1em] \Rightarrow\ \color{90f}{{-}908} \ =\ \color{#0a0}{2 - 910} &\,=\, \color{#c00}{93-1001}\end{align}\ $ so it's trivial by by CCRT
$\Rightarrow \begin{align} -\color{90f}{908}\ \equiv\ \color{#0a0}2&\equiv x \!\!\!\pmod{\!\color{#0a0}{910}}^{\phantom{|^{|^{|^.}}}}\\[.1em] -\color{90f}{908}\equiv \color{#c00}{93} &\equiv x\!\!\!\pmod{\!\color{#c00}{1001}}\end{align}\!\!\!\iff \color{90f}{-908}\equiv x\smash[t]{\pmod{\!\overbrace{{\rm lcm}(910,1001)}^{1001(10)}}} $

Remark $ $ Generally this CRT optimization works for linearly related values and moduli.