Results 1 to 4 of 4

Thread: Chinese Remainder Theorem

  1. #1
    Junior Member
    Joined
    Apr 2006
    Posts
    39

    Chinese 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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote 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,
    $\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$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2006
    Posts
    39
    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
    Last edited by darren_a1; Apr 9th 2006 at 04:37 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote 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,
    $\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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 25th 2010, 07:56 PM
  2. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: Jul 31st 2009, 07:34 AM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 23rd 2009, 08:26 PM
  4. Chinese Remainder Theorem 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 26th 2007, 08:00 PM
  5. Chinese Remainder Theorem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Nov 17th 2006, 04:35 PM

Search Tags


/mathhelpforum @mathhelpforum