Results 1 to 2 of 2

Math Help - Questions using mod

  1. #1
    Junior Member
    Joined
    May 2008
    Posts
    50

    Questions using mod

    Its been ages since I have done any maths and im a little rusty. Can someone please show me how to do these?

    (1) Find  17^{-1} mod \ 130
    (2) Hence solve the equation  17x \equiv 123 (mod 130)

    and

    Give the general solution tot he following system of equivalences

     x \equiv 3 (mod \ 5)
     x \equiv 5 (mod \ 7)
     x \equiv 8 (mod \ 12)

    Thanks to anyone who can help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,412
    Thanks
    1328
    Quote Originally Posted by woody198403 View Post
    Its been ages since I have done any maths and im a little rusty. Can someone please show me how to do these?

    (1) Find  17^{-1} mod \ 130
    Search for a number, n, such that 17n= 1 (mod 130). That is the same as saying that 17n= 130m+ 1 or 17n- 130m= 1 for some integers m and n.
    17 divides into 130 7 times with remainder 11.
    11 divides into 17 once with remainder 6.
    6 divides into 11 once with remainder 5.
    5 divides into 6 once with remainder 1.
    That is: 6- 5= 1. From 5= 11- 6, 6- (11- 6)= 2(6)- 11= 1. From 6= 17- 11, 2(17- 11)- 11= 2(17)- 3(11)= 1. Finally, from 11= 130- 7(17), 2(17)- 3(130- 7(17))= 23(17)- 3(130)= 1.

    One solution to 17n- 130m= 1 is n= 23, m= 3. That is 23(17)= 3(130)+1 so 17(23)= 1 (mod 130).

    (2) Hence solve the equation  17x \equiv 123 (mod 130)
    Easy now: Multiply on both sides by 23 (mod 130).

    and

    Give the general solution tot he following system of equivalences

     x \equiv 3 (mod \ 5)
     x \equiv 5 (mod \ 7)
     x \equiv 8 (mod \ 12)

    Thanks to anyone who can help
     x \equiv 8 (mod \ 12) says that x= 12n+ 8. Putting that into x \equiv 5 (mod 7) gives 12n+ 8\equiv 5n+ 1\equiv 5(mod 7) or 5n\equiv 4 (mod 7). 7 is small enough that we don't have to use the Euclidean algorithm above: just checking numbers shows that 5*5= 25\equiv 4 (mod 7). That is, we have n\equiv 5 (mod 7) which means that n= 7k+ 5. Putting that into x= 12n+ 8 gives x= 12(7k+ 5)+ 8= 84k+ 68.

    Now x\equiv 3 (mod 5) becomes 84k+ 68\equiv 4k+ 3\equiv 3 (mod 5) or simply 4k= 0 (mod 3) which means k is a multiple of 3: k= 3j so x= 84k+ 68= 252j+ 68. If we take j= 0, x= 68. It is easy to see that 68= 13(5)+ 3\equiv 3 (mod 5), 68= 9(7)+ 5\equiv 5 (mod 7) and that 68= 5(12)+ 8\equiv 8 (mod 12).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. More log questions
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 31st 2010, 04:58 PM
  2. Please someone help me with just 2 questions?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 4th 2009, 04:55 AM
  3. Some Questions !
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 3rd 2009, 03:09 AM
  4. Replies: 4
    Last Post: July 19th 2008, 07:18 PM
  5. Replies: 3
    Last Post: August 1st 2005, 01:53 AM

Search Tags


/mathhelpforum @mathhelpforum