Results 1 to 3 of 3

Math Help - Extended Euclid's algorithm - multiplicative inverse

  1. #1
    Junior Member
    Joined
    May 2010
    Posts
    26

    Extended Euclid's algorithm - multiplicative inverse

    Hi All,

    Having trouble with using Extended Euclid's algorithm to find multiplicative inverses.
    I dont understand the algorithm and the more i learn about it the more my brain dies haha.

    If someone could answer the following with simple instructions, that would be awesome.




    Compute the multiplicative inverse of 9 under modulo 31 using the Extended Euclid's algorithm
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    \underline{31} = 3\cdot\underline{9}+\underline{4}
    \underline{9}=2\cdot\underline{4}+\underline{1}

    I underlined the "important" numbers, i.e., the initial numbers and the remainders, and I left out ratios. By expressing important numbers (starting with the final remainder 1) through other important numbers, 1 can eventually be expressed as a linear combination of the original two numbers.

    Therefore, 1 = 9-2\cdot 4 = 9-2(31-3\cdot9)=7\cdot9-2\cdot31.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by extatic View Post
    Hi All,

    Having trouble with using Extended Euclid's algorithm to find multiplicative inverses.
    I dont understand the algorithm and the more i learn about it the more my brain dies haha.

    If someone could answer the following with simple instructions, that would be awesome.




    Compute the multiplicative inverse of 9 under modulo 31 using the Extended Euclid's algorithm

    31=9\cdot 3+4

    9=4\cdot 2+1

    4=4\cdot 1\Longrightarrow (31,9)=1\Longrightarrow \exists x,y\in\mathbb{Z}\,s.t.\,\,31x+9y=1 .

    We now "read" back the above Euclides' Algorithm in order to find x,y (from one line before the last since the

    last one only serves to be sure what the gcd is):

    1=9+(-2)\cdot 4=9+(-2)\cdot (31+(-3)\cdot 9)=7\cdot 9+(-2)\cdot 31 , and from here we get at once that

    9\cdot 7=1+31\cdot 2\Longrightarrow 7=9^{-1}\!\!\pmod{31}

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 15th 2012, 11:32 AM
  2. Replies: 4
    Last Post: March 4th 2010, 12:09 PM
  3. Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 29th 2009, 04:54 AM
  4. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 23rd 2008, 09:03 AM
  5. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: April 10th 2008, 05:28 AM

Search Tags


/mathhelpforum @mathhelpforum