Results 1 to 4 of 4

Math Help - Euclidean Algorithm--can't seem to make it work backwards

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    2

    Euclidean Algorithm--can't seem to make it work backwards

    I'm working a problem in my textbook and am stuck. Here's what I have so far:
    GCD (34, 58)
    58 = 34 x 1 + 24
    34 = 24 x 1 + 10
    24 = 10 x 2 + 4
    10 = 4 x 2 + 2 = GCD (4, 2)

    So working backwards:

    2 = 10 - 4 x 2
    = 10 - (24 - 10 x 2) x 2
    = 10 x 2 - 24 + 10 x 2
    = 10 x 4 - 24
    = (34 - 24) x 4 - 24

    And that's where I get lost. I work it through and cannot seem to get the right answer. I know that I need to get 12 to go with a and 7 to go with b, but how do I express this going backwards using the algorithm? There must be some mistake I'm making. Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Quote Originally Posted by cathy1988 View Post
    So working backwards:

    2 = 10 - 4 x 2
    = 10 - (24 - 10 x 2) x 2
    = 10 x 2 - 24 + 10 x 2 What happened here??
    = 10 x 4 - 24
    = (34 - 24) x 4 - 24
    (In red)

    10 - \left[24 - 2(10)\right](2) \ = \ 10 - 24(2) + 4(10) \ = \ 5(10) - 2(24) = \hdots
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2008
    Posts
    2
    OK, my professor obviously never explained how to handle these tougher algorithms. So using what you've given me, I now have:

    2 = 10(5) - 24(2)

    And I'm lost. Which of these do I substitute (34-24) into? Is it 10 x 5 or 24 x 2 or both?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by cathy1988 View Post
    OK, my professor obviously never explained how to handle these tougher algorithms. So using what you've given me, I now have:

    2 = 10(5) - 24(2)

    And I'm lost. Which of these do I substitute (34-24) into? Is it 10 x 5 or 24 x 2 or both?
    you want a combination of 2 and 4, so if there is a 2, leave it, anything but 2 or 4 you change

    see post #8 here
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 5th 2011, 05:59 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 24th 2010, 09:54 PM
  3. Simplex algorithm, working backwards, help asap!
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 6th 2010, 07:33 AM
  4. Replies: 1
    Last Post: September 30th 2008, 10:23 AM
  5. Euclidean algorithm gcd lcm help..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 10th 2006, 05:46 AM

Search Tags


/mathhelpforum @mathhelpforum