Results 1 to 2 of 2

Math Help - chinese remainder

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    124

    chinese remainder

    1) Make a list of the units in Z16, and with each unit give its multiplicative inverse.

    2) Solve the following system of congruences
    X=2 (mod 3)
    X=3 (mod 5)
    X=6 (mod 7)
    3) Solve the following system of congruences
    X=2 (mod 3)
    X=3 (mod 5)
    X=4 (mod 7)
    X=5 (mod 11)
    Any help would be great.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,693
    Thanks
    1466
    Quote Originally Posted by noles2188 View Post
    1) Make a list of the units in Z16, and with each unit give its multiplicative inverse.
    This is just "arithmetic" If, for example, 3 and x are multiplicative inverses, then 3x= 1 (mod 16) so 3x= 16n+ 1. 16+ 1= 17 is not a multiple of 16 but 2(16)+ 1= 33 is. It is 3(11) so the multiplicative inverse of 3 is 11. Similarly 16n+ 1 is a multiple of 5 for n= 4: 16(4)+ 1= 65= 5(13) so the multiplicative inverse of 5 is 13. 16(3)+1= 49= 7(7) so 7 is its own multiplicative inverse. 5(16)+ 1= 81= 9*9 so 9 is also its own multiplicative inverse. 15*15= 225= 14(16)+ 1 so 15 is also its own multiplicative inverse.

    If p is even, then px- 16n is divisible by 2 no matter what x and n are so we can never have px- 16n= 1 or px= 16n+ 1. What does that tell you?

    [2) Solve the following system of congruences
    X=2 (mod 3)
    X=3 (mod 5)
    X=6 (mod 7)

    Those tell you that X= 3a+ 2= 5b+ 3= 7c+ 6 for integers a, b, c. Just looking at possible values for c, I find that 7(11)+ 6= 5(13)+ 3= 3(27)+ 2.

    3) Solve the following system of congruences
    X=2 (mod 3)
    X=3 (mod 5)
    X=4 (mod 7)
    X=5 (mod 11)
    Any help would be great.
    Again, these equations tell you that X= 3a+ 2= 5b+ 3= 7c+ 4= 11d+ 5 for integer. Trying succesive values for d I find that 11(33)+5= 7(52)+ 4= 5(13)+ 3= 3(122)+ 2= 368.

    For a more systematic way of doing these look up the "Chinese Remainder Theorem".
    Last edited by HallsofIvy; October 29th 2008 at 10:09 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: June 21st 2011, 06:47 AM
  2. The chinese remainder theorem.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: June 12th 2011, 07:52 PM
  3. Chinese Remainder Thm
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: April 8th 2010, 12:37 PM
  4. CRT(chinese remainder theorem)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 19th 2009, 09:01 PM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: July 31st 2009, 07:34 AM

Search Tags


/mathhelpforum @mathhelpforum