# Chinese Remainder Theorem

• November 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?
• November 22nd 2009, 04:37 PM
galactus
We can rewrite them as:

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

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

From these we can write:

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

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

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

$b=7c+1$

Sub into the right side of [1]:

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

The solutions to the system are:

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

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

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