0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ $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. $\endgroup$ Nov 30 '19 at 6:56
  • $\begingroup$ Hint: $ $ It's trivial since $\ 93-2 = 1001-910\ $ so $\ x\equiv 910 -2 = 1001-93,\ $ see my answer. $\endgroup$ Nov 30 '19 at 7:04
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Nov 30 '19 at 15:08
1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Much easier to exploit CCRT - see my answer. $\endgroup$ Nov 30 '19 at 6:55
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.