Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$


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

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

share|cite|improve this question
Do you really mean $x=-3 (mod 1)$ ? – user127.0.0.1 Nov 29 '12 at 16:47
yes i have but the details i have on it dont go into what to do next! – Stephanie Jones Nov 29 '12 at 16:55

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$

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer
ok thnak you i shall have another look through. – Stephanie Jones Nov 29 '12 at 17:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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