Results 1 to 2 of 2

Math Help - Inverse of a modulo

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    83

    Inverse of a modulo

    Find the inverse of modulo 125. Hence solve 43x = 3 mod 125?

    where " = " indicates equivalent to

    Firstly, I find gcd (125,43) = 1
    By Euclid's algorithm, we have

    125 = 43(2) + 39
    43 = 39(1) + 4
    39 = 4(9) + 3
    4 = 3(1) +1

    so, working backwards we get:
    1 = 4 - 3(1)
    = 4 -[39 - 4(9)](1)
    = 4(10) - 39(1)
    = [43 - 39(1)](10) - 39(1)
    = 43(10) - 39(11)
    = 43(10) - [125 - 43(2)](11)
    = 43(32) - 125(11)

    This means 32 is the inverse of 43 and -11 is the inverse of 125. Are these the correct results ?

    After this, how can I solve the equation 43x = 3 mod 125?

    Is there a quick way to find the inverse of a modulo m , apart from Euclid's algorithm
    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 knguyen2005 View Post
    1 = 4 - 3(1)
    = 4 -[39 - 4(9)](1)
    = 4(10) - 39(1)
    = [43 - 39(1)](10) - 39(1)
    = 43(10) - 39(11)
    = 43(10) - [125 - 43(2)](11)
    = 43(32) - 125(11)

    This means 32 is the inverse of 43 and -11 is the inverse of 125. Are these the correct results ?
    This means 43(32) \equiv 1 (\bmod 125) therefore 32 is inverse of 43.

    After this, how can I solve the equation 43x = 3 mod 125?
    Multiply both sides by 32 and this gives 32(43x) \equiv 32(3) (\bmod 125) \implies x \equiv 96 (\bmod 125).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] inverse in modulo 26
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 9th 2011, 02:52 PM
  2. inverse of 4 modulo 9
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 17th 2009, 07:40 AM
  3. inverse of modulo
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 22nd 2009, 08:03 PM
  4. (n) inverse modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 21st 2009, 11:49 AM
  5. inverse modulo
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 15th 2008, 02:31 PM

Search Tags


/mathhelpforum @mathhelpforum