Wednesday, December 22, 2010

2010/065) an example of chinese remainder theorem

What would be the least total no. which give the remainder 1,2 and 3 when divided by 7,9 and 11?

1,2 and 3 when divided by 7,9 and 11?

hence
x= 1 mod 7
x= 2 mod 9
x =3 mod 11

now 7 ,9 and 11 are pair wise coprime

x = 1 a1b1 + 2 a2b2 + 3 a3b3 mod 7*9*11(or 693)


where a1 = 9*11 = 99
a2 = 7 * 11 = 77
a3 = 7 * 9 = 63

and
a1b1 = 1 mod 7
a2b2 = 1 mod 9
a3b3 = 1 mod 11

a1 = 99 so b1 = 99 mod 7 or 1 mod 7 so b1 = 1

77b2 mod 9 = 1 so 5b2 mod 9 = 1 so b2= 2 (as 5*2 = 10 mod 9)

63b3 = 1 mod 11 or 8b3 =1 mod 11 so b3 = 7 as 7 * 8 = 56 = 1 mod 11

So x = 1 * 99 * 1 + 2 * 77 * 2 + 3 * 63 * 7 mod 693 = 1730 mod 693

= 344 mod 693

So x if of the form 693n + 344 or lowest x = 344
at

7 comments:

  1. AasthaJanuary 5, 2011 at 8:11 PM

    wowwwwwww! great blog :D

    ReplyDelete
  2. gautami tripathyJanuary 7, 2011 at 11:01 PM

    Big brother, you mis-spelled Chinese!

    :D

    ReplyDelete
  3. kaliprasad January 8, 2011 at 3:03 PM

    the spelling is corrected (Chinese)

    ReplyDelete
  4. jyothymj@gmail.comFebruary 17, 2012 at 11:37 PM

    I tried your method with remainders = 1,2,4 and moduli (5,7,9) and it doesn't work! What you illustrated must be an exemption I think.

    ReplyDelete
  5. kaliprasad February 27, 2012 at 8:21 PM

    here is the solution (steps are not explained same as above)
    X =1 mod 5
    X = 2 mod 7
    X = 4 mod 9

    5 , 7, 9 are pairwise co-prime
    5 * 7 * 9 = 315

    Now 7 * 9 = 63 = 3 mod 5 so inversion wrt 5 = 2 as 3 * 2 = 6 = 1 mod 5
    5 * 9 = 45 = 3 mod 7 so inversion = 5
    5 * 7 = 35 = - 1 mod 9 so inversion = -1 or 8 mod 9
    (applying above logic)
    So x= 1 * 63 * 2 + 2 * 45 * 5 + 4 * 35 * 8 mod 315
    = 126 + 450 + 1120 mod 315
    = 1696 mod 315 = 121

    121 satisfies the condition

    ReplyDelete
  6. UnknownMarch 3, 2012 at 4:57 PM

    find the number which divided by 7,9,13,15,17 give remainder 1,2,3,4,5..i m not getting the answer ...

    ReplyDelete
  7. UnknownSeptember 16, 2014 at 7:10 PM

    good example..thank you

    ReplyDelete