# Linear combinations of integers

• June 14th 2008, 12:27 PM
sjenkins
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.
• June 14th 2008, 01:02 PM
Opalg
Quote:

Originally Posted by sjenkins
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
• June 14th 2008, 01:23 PM
sjenkins
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
• June 14th 2008, 01:29 PM
topsquark
Quote:

Originally Posted by sjenkins
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
• June 14th 2008, 01:36 PM
sjenkins
• June 14th 2008, 03:17 PM
sjenkins
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.