Thread: linear combination ?

I have a question that involves two parts. I believe I have the first part correct. The second part is what I am confused on and explain below.

a) Find the gcd(260,154)

260 = 1(154) + 106
154 = 1(106) + 48
106 = 2(48) +10
48 = 4(10) + 8
10 = 1(8) + 2
8 = 4(2) + 0

Thus the gcd(260,154) is 2 since it is the last non-zero remainder.

***b) Find integers such that 154x + 260y = 4

Well, usually I would use part a and find the line with 4 as a remainder and work backwards until I find x and y. My problem is that I don’t have 4 as a remainder in any of the lines above and therefore I am not sure what to do? I may have calculated the gcd incorrectly, but I have checked it several times and get the same answer. Also, my book examples find x and y differently than the way I am being taught. Any suggestions? Thanks!

Originally Posted by MathStudent1

***b) Find integers such that 154x + 240y = 4

240=154(1)+86
154=86(1)+68
86=68(1)+18
18=14(1)+4
14=4(3)+2
4=2(2)

---------

2=14-4(3)
2=(68-18(3))-(18-14)(3)
2=68-18(6)+14(3)
2=(154-86)-(86-68)(6)+(68-18(3))(3)
2=154-86(7)+68(9)-18(9)
2=154-(240-154)(7)+(154-86)(9)-(86-68)(9)
2=-240(7)+154(17)-86(18)+68(9)
2=-240(7)+154(7)-(240-154)(18)+(154-86)(9)
2=-240(25)+154(44)-(240-154)(9)
2=-240(34)+154(53)
2=240(-34)+154(53)

240(-68)+154(106)=4

can you see what i did?

Originally Posted by frenzy

240=154(1)+86
154=86(1)+68
86=68(1)+18
18=14(1)+4
14=4(3)+2
4=2(2)

---------

2=14-4(3)
2=(68-18(3))-(18-14)(3)
2=68-18(6)+14(3)
2=(154-86)-(86-68)(6)+(68-18(3))(3)
2=154-86(7)+68(9)-18(9)
2=154-(240-154)(7)+(154-86)(9)-(86-68)(9)
2=-240(7)+154(17)-86(18)+68(9)
2=-240(7)+154(7)-(240-154)(18)+(154-86)(9)
2=-240(25)+154(44)-(240-154)(9)
2=-240(34)+154(53)
2=240(-34)+154(53)

240(-68)+154(106)=4

can you see what i did?

Frenzy, I made a TYPO!! I wrote part a correct and messed up part b. It should read 154x + 260y = 4. So, how would you do it using 260 instead of 240? Thanks!

Originally Posted by MathStudent1

Frenzy, I made a TYPO!! I wrote part a correct and messed up part b. It should read 154x + 260y = 4. So, how would you do it using 260 instead of 240? Thanks!

2=10-8
2=(106-48(2))-(48-10(4))
2=106-48(3)+10(4)
2=(260-154)-(154-106)(3)+(106-48(2))(4)
2=260-154(4)+106(7)-48(8)
2=260-154(4)+(260-154)(7)-(154-106)(8)
2=260(8)-154(19)+106(8)
2=260(8)-154(19)+(260-154)(8)
2=260(16)-154(27)
2=260(16)+154(-27)
4=260(32)+154(-54)

How's that?

Just to clarify my thinking. In the last line when you multiply through by 2 to both sides on the RHS you multiply 16 and -27 by two and not 260 and 154 to achieve the desired linear combination. I think I get it. Thanks!

Originally Posted by MathStudent1

Just clarify one thing. In the last line when you multiply through by 2 to both sides one the RHS you multiply 16 and -27 by two and not 260 and 154 to achieve the desired linear combination.

Correct