Results 1 to 6 of 6

Math Help - Linear combinations of integers

  1. #1
    Member
    Joined
    May 2008
    Posts
    109

    Question Linear combinations of integers

    Express the greatest common divisor of each of the following pairs of integers as a linear combination of these integers. 34,55

    Here's what I have so far

    55=34*1+21
    34=21*1+13
    21=13*1+8
    13=8*1+5
    8=5*1+3
    5=3*1+2
    3=2*1+1
    2=1*2

    Making 1 the greatest common divisor.

    I also know that to solve this, you have to solve for the remainders so....

    1=3-1*2
    1=3-1(5-1*3)
    1=3-1((5-1)(8-1*5))
    1=3-1((5-1)(8-1)(13-1*8))
    1=3-1((5-1)(8-1)(13-1)(21-1*13))
    1=3-1((5-1)(8-1)(13-1)(21-1)(34-1*21))

    I think I have it right so far, the answer to the question per the back of the book is 1=13*55+(-21)*34. This is where my problem is, I just can't see where the answer is coming from. I think I have it set up, but the end is confusing me.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by sjenkins View Post
    Express the greatest common divisor of each of the following pairs of integers as a linear combination of these integers. 34,55

    Here's what I have so far

    55=34*1+21
    34=21*1+13
    21=13*1+8
    13=8*1+5
    8=5*1+3
    5=3*1+2
    3=2*1+1
    2=1*2

    Making 1 the greatest common divisor.

    I also know that to solve this, you have to solve for the remainders so....

    1=3-1*2
    1=3-1(5-1*3)
    1=3-1((5-1)(8-1*5)) Wrong. Should be 3-1(5-1(8-1*5))
    1=3-1((5-1)(8-1)(13-1*8))
    1=3-1((5-1)(8-1)(13-1)(21-1*13))
    1=3-1((5-1)(8-1)(13-1)(21-1)(34-1*21)) Parentheses are getting more and more mixed up!
    Do it like this, multiplying out the brackets as you go along:

    1 = 3 - 2*1 = 3 - 2
    1 = 3 - (5 - 3) = (-1)*5 + 2*3
    1 = (-1)*5 + 2*(8 - 5) = 2*8 - 3*5
    1 = 2*8 - 3*(13 - 8) = (-3)*13 + 5*8
    1 = (-3)*13 + 5*(21 - 13) = 5*21 - 8*13
    1 = 5*21 - 8*(34 - 21) = (-8)*34 + 13*21
    1 = (-8)*34 + 13*(55 - 34) = 13*55 - 21*34
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    109
    Now I'm even more confused, I know there is just something that is not clicking.

    1 = 3 - 2*1 = 3 - 2
    1 = 3 - (5 - 3) = (-1)*5 + 2*3 (where does this -1 come from?)
    1 = (-1)*5 + 2*(8 - 5) = 2*8 - 3*5
    1 = 2*8 - 3*(13 - 8) = (-3)*13 + 5*8
    1 = (-3)*13 + 5*(21 - 13) = 5*21 - 8*13
    1 = 5*21 - 8*(34 - 21) = (-8)*34 + 13*21
    1 = (-8)*34 + 13*(55 - 34) = 13*55 - 21*34
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,855
    Thanks
    321
    Awards
    1
    Quote Originally Posted by sjenkins View Post
    1 = 3 - (5 - 3) = (-1)*5 + 2*3 (where does this -1 come from?)
    3 - (5 - 3) = 3 + (-1)(5 - 3)

    = 3 + (-1) \cdot 5 + (-1) \cdot -3

    = 3 + (-1) \cdot 5 + 3

    = (-1) \cdot 5 + 2 \cdot 3

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2008
    Posts
    109
    Thank you, now I see that, but...







    why is this 2*3 instead of 3+3? Are you just trying to keep it in simplest form?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2008
    Posts
    109

    Red face

    Never mind...thank you all for your help, but I found a different way to figure this out with a table. I still can't understand the way shown here, but as long as I have a way to figure it out, I guess I'm ok.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Linear Combinations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 1st 2010, 03:36 AM
  2. [SOLVED] Linear combinations
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: July 22nd 2010, 07:34 AM
  3. Linear combinations
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: May 6th 2009, 05:04 PM
  4. linear combinations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 10th 2009, 06:49 AM
  5. Linear combinations?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 27th 2006, 04:20 PM

Search Tags


/mathhelpforum @mathhelpforum