have a problem on hand - this one is kinda easy- but am stuck :P

the problem is :

Solve using CRT:

x congruent to 8(mod13)

x congruent to 1(mod 5)

x congruent to 5 (mod 6)

i have gotten most of it. just want to be sure

thanks

Printable View

- Apr 9th 2006, 03:39 PMdarren_a1Chinese Remainder Theorem
have a problem on hand - this one is kinda easy- but am stuck :P

the problem is :

Solve using CRT:

x congruent to 8(mod13)

x congruent to 1(mod 5)

x congruent to 5 (mod 6)

i have gotten most of it. just want to be sure

thanks - Apr 9th 2006, 04:07 PMThePerfectHackerQuote:

Originally Posted by**darren_a1**

$\displaystyle x\equiv 8 \mod 13$

$\displaystyle x\equiv 1 \mod 5 $

$\displaystyle x\equiv 5\mod 6$

Also, $\displaystyle \gcd(13,5)=\gcd(5,6)=\gcd(13,6)=1$

thus, we may rely on Chinese Remainder Theorem.

----

By Chinese Remainder Theorem, we know that,

$\displaystyle x\equiv a_1b_1N_1+a_2b_2N_2+a_2b_3N_3 \mod N$

Where,

$\displaystyle N=5\cdot 6\cdot 13$

$\displaystyle N_1=N/13=30$

$\displaystyle N_2=N/5=78$

$\displaystyle N_3=N/6=65$

Also,

$\displaystyle a_1=8$

$\displaystyle a_2=1$

$\displaystyle a_3=5$

Finally,

$\displaystyle b_1\cdot N_1\equiv 1 \mod 13$ thus, $\displaystyle b_1=10$

$\displaystyle b_2\cdot N_2\equiv 1\mod 5$ thus, $\displaystyle b_2=2$

$\displaystyle b_3\cdot N_3\equiv 1\mod 6$ thus, $\displaystyle b_3=5$

Thus,

$\displaystyle x\equiv 2400+156+1625\equiv 4181 \mod 390$

Thus,

$\displaystyle x\equiv 281\mod 390$ - Apr 9th 2006, 04:33 PMdarren_a1
Thanks! That was awesome - this was a problem in m Discrete Math class - so i posted it here! Sorry for trouble caused - am still a bit confused as to how you calculate b1 b2 and b3 :(

Cheers - Apr 10th 2006, 07:28 AMThePerfectHackerQuote:

Originally Posted by**darren_a1**

$\displaystyle

\left\{ \begin{array}{c}b_1\cdot N_1\equiv 1 \mod 13\\

b_2\cdot N_2\equiv 1\mod 5\\

b_3\cdot N_3\equiv 1\mod 6\end{array}\right

$.

Is your problem based on*how*to solve these congruences.