Results 1 to 3 of 3

Thread: 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,577
    Thanks
    790
    $\displaystyle \underline{31} = 3\cdot\underline{9}+\underline{4}$
    $\displaystyle \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, $\displaystyle 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
    3
    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

    $\displaystyle 31=9\cdot 3+4$

    $\displaystyle 9=4\cdot 2+1$

    $\displaystyle 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 $\displaystyle x,y$ (from one line before the last since the

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

    $\displaystyle 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

    $\displaystyle 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: Jan 15th 2012, 11:32 AM
  2. Replies: 4
    Last Post: Mar 4th 2010, 12:09 PM
  3. Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Mar 29th 2009, 04:54 AM
  4. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 23rd 2008, 09:03 AM
  5. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Apr 10th 2008, 05:28 AM

Search Tags


/mathhelpforum @mathhelpforum