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

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?

• $910=91\cdot10$ and $1001=91\cdot11$, so the relevant coprime moduli are $10,11$ and $91$, the last being the greatest common factor. Luckily the given congruences are compatible modulo the gcd as $93\equiv2\pmod{91}$. CRT does the rest. Nov 30 '19 at 6:56
• Hint:  It's trivial since $\ 93-2 = 1001-910\$ so $\ x\equiv 910 -2 = 1001-93,\$ see my answer. Nov 30 '19 at 7:04

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.

• Yes, the general algorithm / formula works easily enough here, but in this case there is special structure that makes it completely trivial - see my answer. Nov 30 '19 at 15:08

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

• Much easier to exploit CCRT - see my answer. Nov 30 '19 at 6:55

\!\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.

• and $\bmod 10010\!:\ \color{#0a0}{{-}908}\equiv 10010-908\equiv 9102\ \$ Nov 30 '19 at 6:53