Results 1 to 3 of 3

Math Help - Euclidean Algorithm

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    21

    Euclidean Algorithm

    Use the Euclidean Algorithm to find the multiplicative inverse of 17 in Z31:
    So Ive done MOST of the calculations,
    a=17 p=31
    ..... I then get 1=(11)17-(6)31 [note 31=0 in Z31]
    so 1=(11)17 Butt 11 in Z31 is -20?
    so 11(-20)=-340
    -340=1 mod (31) or... is the answer 340= -1 mod (31)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: Euclidean Algorithm

    You have found that 11\cdot 17 = 1 in \mathbb{Z}_{31}. What is the definition of a multiplicative inverse?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Re: Euclidean Algorithm

    Quote Originally Posted by farmeruser1 View Post
    Use the Euclidean Algorithm to find the multiplicative inverse of 17 in Z31:
    So Ive done MOST of the calculations,
    a=17 p=31
    ..... I then get 1=(11)17-(6)31 [note 31=0 in Z31]
    so 1=(11)17 Butt 11 in Z31 is -20?
    so 11(-20)=-340
    -340=1 mod (31) or... is the answer 340= -1 mod (31)
    As a note, this should be in Number Theory.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 30th 2010, 10:46 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2010, 06:53 AM
  3. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 06:45 PM
  4. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 03:20 AM
  5. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 08:28 AM

Search Tags


/mathhelpforum @mathhelpforum