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 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|cite|improve this question
Can you give at least some ideas? – DonAntonio Nov 28 '12 at 13:44

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

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

Solving the first and second equations simultaneously, you get x= 17 mod 40. Solving the third and fourth equations simultaneously, you get x = 52 mod 99. Solving these two results simultaneously, you get x = 1537 mod 3960 which gives you all possible solutions.

share|cite|improve this answer


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

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.