1
$\begingroup$

Solve $x\equiv 2\pmod 5, x\equiv 1\pmod 8, x\equiv 7\pmod 9, x\equiv -3\pmod {11}$ for $x\in\mathbb Z$.

$x\equiv a_i\pmod {m_i}$

The system of congruences has a unique solution modulo M($m_1, m_2, m_3, m_4$)

$x:= a_1\frac{M}{m_1}b_1+a_2\frac{M}{m_2}b_2+a_3\frac{M}{m_3}b_3+a_4\frac{M}{m_4}b_4$

$x:= 2\frac{M}{5}b_1+\frac{M}{8}b_2+7\frac{M}{9}b_3-3\frac{M}{11}b_4$

$M=3960$

$x:= 1584b_1+495b_2+3080b_3-1080b_4$

I am not sure what i should do next to solve for $b_i$...

  • 0
    yes i have but the details i have on it dont go into what to do next!2012-11-29

3 Answers 3

1

Hint $\rm\ mod\ 8,11\!:\ 2x \equiv -6,\:$ so $\rm\:x \equiv -3\ (mod\ 44),\:$ so $\rm\:x\equiv \color{blue}{-47\ (mod\ 88)}\: $ by $\rm\:x\equiv 1\ (mod\ 8)$

$\rm\qquad\ \ mod\ 9\!:\ {-}2 \equiv x \equiv\color{blue}{-47+88\,n}\,\ \equiv\ {-}2-2n,\:$ so $\rm\: n\equiv 0,\:$ i.e. $\rm\: n = \color{#0A0}{9k}$

$\rm\qquad\ \ mod\ 5\!:\ \ \ \ 2 \equiv x \equiv -47+88\!\cdot\!\color{#0A0}{9k}\equiv -2+2k,\:$ so $\rm\: k\equiv \color{#C00}2,\ \ $ therefore

$\rm\ \ \ mod\,\ 5\cdot 8\cdot 9\cdot 11\!:\ x \equiv -47+88\cdot 9\cdot\color{#C00}2\equiv 1537$

0

To do it by hand, I would start by looking through the numbers $\equiv 2 \pmod 5$ until I found one that was $\equiv 1 \pmod 8$. You won't have to look at more than $8$ of them. Among $2,7,12,17 \ldots$ we find $17$. Now we know the solution is $\equiv 17 \pmod {40}$. So look through those for one that is $\equiv 7 \pmod 9$. There is an automated way with the extended Euclidean algorithm which is more appropriate if you have larger numbers or many problems.

0

You need to look at your notes or textbook again and find the definition of the $b_i$. These are solutions of the congruences $b_i \equiv 1 \mod m_i, \, b_i \equiv 0 \mod m_j \, (j \ne i)$ and they have to be computed first.

  • 0
    ok th$n$ak you i shall have another look through.2012-11-29