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 the following system of congruences: $$x \equiv 2 \pmod 5$$ $$x \equiv 1 \pmod8$$ $$x \equiv 7 \pmod 9$$ $$\quad x \equiv -3 \pmod {11}$$

i have no idea how to go about starting this, any help would be much appreciated.

share|improve this question
1  
Can you give at least some ideas? –  DonAntonio Nov 28 '12 at 13:44
add comment

3 Answers

For example

$$x=2\pmod 5\Longleftrightarrow \,\exists\,\, k\in\Bbb Z\,\,\,s.t.\,\,x=2+5k$$

$$x=1\pmod 8\Longleftrightarrow\,\,\exists\,\,m\in\Bbb Z\,\,\,s.t.\,\,\,x=1+8m$$

and etc.

You can continue with this, form some equations and find some solution...or else you can use the powerful and nice CRT = Chinese Remainder Theorem, and in particular its proof , and do it faster, cleaner and nicer.

share|improve this answer
    
how would i go about using the CRT method?? i have the M value = 2 x 8 x 9 x 11 = 3960 ... i divide the M value by each mod value and find its congruents ... i am left with 792=2 mod 5, 495=7 mod 8, 440=8 mod 9, 360=8 mod 11... by dont know where to go from here?? –  jill Nov 28 '12 at 15:22
    
In the site I linked to you look under"A constructive algorithm to find the solution". It's pretty simple, but of course: there's some work to do. I got the solution $\,x= 1,537\,$ –  DonAntonio Nov 28 '12 at 17:23
add comment

Another option is using the linear diophantine equation $5a-8b=-1$. Because $x=5a+2=8b+1$.

This will give a certain condition for $a$ of the shape $a=8k+k_a$, where $k_a$ is a constant. So $x=40k+(5k_a+2)$, or $x\equiv 5k_a+2\pmod{40}$.

This reduces the first two equations to only one. If you repeat this twice you will finally obtain something of the shape $x\equiv p\pmod{q}$

share|improve this answer
add comment

Hint

Consider the solution to $$ \begin{align} x&\equiv1\pmod{5}\\ x&\equiv0\pmod{8}\\ x&\equiv0\pmod{9}\\ x&\equiv0\pmod{11}\\ \end{align}\tag{1} $$ Suppose we can solve $$ 5a+792b=1\tag{2} $$ then $x\equiv792b\pmod{3960}$ would satisfy $(1)$. We can use the Euclid-Wallis Algorithm to solve $(2)$: $$ \begin{array}{r} &&158&2&2\\\hline 1&0&1&\color{#C00000}{-2}&\color{#C00000}{5}\\ 0&1&-158&317&-792\\ 792&5&2&1&0\\ &&&{\uparrow}&{\star} \end{array}\tag{3} $$ $(3)$ tells us that $b\equiv-2\equiv3\pmod{5}$ satisfies $(2)$. Thus, $x\equiv2376\pmod{3960}$ satisfies $(1)$.

There are three other sets of equations corresponding to $(1)$ that can be solved and then combined to get the solution to your problem.

share|improve this answer
add comment

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.