Chinese Remainder Theorem

**darren_a1** · April 9th 2006, 03:39 PM

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

**ThePerfectHacker** · April 9th 2006, 04:07 PM

Originally Posted by darren_a1

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

We have,
$x\equiv 8 \mod 13$
$x\equiv 1 \mod 5$
$x\equiv 5\mod 6$
Also, $\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,
$x\equiv a_1b_1N_1+a_2b_2N_2+a_2b_3N_3 \mod N$
Where,
$N=5\cdot 6\cdot 13$
$N_1=N/13=30$
$N_2=N/5=78$
$N_3=N/6=65$
Also,
$a_1=8$
$a_2=1$
$a_3=5$
Finally,
$b_1\cdot N_1\equiv 1 \mod 13$ thus, $b_1=10$
$b_2\cdot N_2\equiv 1\mod 5$ thus, $b_2=2$
$b_3\cdot N_3\equiv 1\mod 6$ thus, $b_3=5$

Thus,
$x\equiv 2400+156+1625\equiv 4181 \mod 390$
Thus,
$x\equiv 281\mod 390$

**darren_a1** · April 9th 2006, 04:33 PM

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

**ThePerfectHacker** · April 10th 2006, 07:28 AM

Originally Posted by darren_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

First, do you understand that those are the numbers that solve the congruences,
$<br /> \left\{ \begin{array}{c}b_1\cdot N_1\equiv 1 \mod 13\\<br /> b_2\cdot N_2\equiv 1\mod 5\\<br /> b_3\cdot N_3\equiv 1\mod 6\end{array}\right<br />$ .
Is your problem based on how to solve these congruences.

Thread: Chinese Remainder Theorem

LinkBack

Thread Tools

Display