Chinese Remainder Theorem

• Nov 22nd 2009, 01:19 PM
steph3824
Chinese Remainder Theorem
2x http://www.mathhelpforum.com/math-he...1340c453-1.gif1 (mod 7)
5x http://www.mathhelpforum.com/math-he...1340c453-1.gif2 (mod 11)

I know how to do the CRT, but the fact that this prob. has coefficients in front of the x is confusing me. How do I go about solving this?
• Nov 22nd 2009, 04:37 PM
galactus
We can rewrite them as:

$\displaystyle 2x\equiv 1\equiv 8 (mod \;\ 7)\Rightarrow \boxed{x\equiv 4(mod \;\ 7)}$

$\displaystyle 5x\equiv 2\equiv 13\equiv 24\equiv 35(mod 11)\Rightarrow \boxed{x\equiv 7(mod \;\ 11)}$

From these we can write:

$\displaystyle 7a+4=11b+7$...[1]

Appyling modulo 7 to $\displaystyle 7a+4=11b+7$ and we get:

$\displaystyle b\equiv 1(mod \;\ 7)$

$\displaystyle b=7c+1$

Sub into the right side of [1]:

$\displaystyle 11(7c+1)+7=77c+18$

The solutions to the system are:

$\displaystyle x\equiv 18(mod \;\ 77)$

Which can be written as $\displaystyle \boxed{x=77t+18}$

Let $\displaystyle t=0,1,2,......$ and they will satisfy the system of linear congruences.
• Nov 22nd 2009, 05:00 PM
steph3824