Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|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

3 Answers 3

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|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|improve this answer
    
ok thnak you i shall have another look through. –  Stephanie Jones Nov 29 '12 at 17:29

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|improve this answer

Your Answer

 
discard

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.