Results 1 to 6 of 6

Thread: 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
    10
    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
    11,019
    Thanks
    686
    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: Oct 1st 2010, 03:36 AM
  2. [SOLVED] Linear combinations
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Jul 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: Mar 10th 2009, 06:49 AM
  5. Linear combinations?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Feb 27th 2006, 04:20 PM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum