Chinese Remainder Theorem

**steph3824** · November 22nd 2009, 01:19 PM

2x

1 (mod 7)
5x

2 (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?

**galactus** · November 22nd 2009, 04:37 PM

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.

**steph3824** · November 22nd 2009, 05:00 PM

I see...thanks for your help!

Thread: Chinese Remainder Theorem

LinkBack

Thread Tools

Display