Thread: Linear combination please help

gcd (42,660 )

660 = 41*16 + 4
41 = 4 * 10 + 1
4 = 1 * 4 + 0

so gcd ( 42, 660 ) = 1

How do express it as linear combination of 41 and 660. I know i work backward....and i get this far and i get stuck..

1 = 41-4*10
1 = 41-(660-41*16)*10

After that...i have no idea what to. I have been reading the examples and problems people have done on this site but i just can't figure out where their numbers are coming from. Any help would be appreciated...Thank you

Originally Posted by smoothi963

gcd (42,660 )

660 = 41*16 + 4
41 = 4 * 10 + 1
4 = 1 * 4 + 0

so gcd ( 42, 660 ) = 1

No wonder you cannot get the right answer, you got the greatest commond divisor all wrong.

Watch frum die meister und lern.

660=15*42+30
42=1*30+12
30=2*12+6
12=2*6+0
Thus, gcd(42,660)=6.

Now linear combinations:

30-2*12=6
30-2(42-30)
30-2*42+2*30=3*30-2*42=6
3(660-15*42)-2*42=6
3*660-47*42=6

Thank you....lol i am so retarded. >.<