1
$\begingroup$

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.

  • 1
    Can you give *at least* some ideas?2012-11-28

4 Answers 4

2

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.

  • 0
    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\,$2012-11-28
1

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

1

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.

0

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.