Thread: Number Theory GCD Linear Combination

Hi again (as you can tell, I've been working on this stuff all day, sorry for posting so much!)

Right now I'm working on a Linear Combinations problem.

Here's the problem:
Write GCD(1326,252) as a linear combination of 1326 and 252.

Here's what I have:

Find the GCD:
1326 = 5 * 252 + 66
252 = 3 * 66 + 58
66 = 1 * 58 + 8
58 = 7 * 8 + 2
8 = 4 * 2 + 0 so 2 is the GCD

Now work backwards:
2 = 58 - 7 * 8
8 = 66 - 1 * 58
58 = 252 - 3 * 66
66 = 1326 - 5 * 252

Substitute: *this is where I'm having problems!
2 = 58 - 7 * 8
= 58 - 7 * ( 66 - 1 * 58 )
= 8 ( 58 ) - 7 ( 66 ) <--- but I need it in 1326,252 form, so I continue...
= 8 ( 252 - 3 * 66 ) - 7 ( 1326 - 5 * 252 )
= 8 ( 252 - 3 ( 1326 - 5 * 252 ) - 7 ( 1326 - 5 * 252 )
= 8 ( 252 ) - 24 ( 1326 - 5 * 252 ) - 7 ( 1326 ) + 35 ( 252 )
= 8(252) -24(1326) +120(252) -7(1326) +35(252)
= 163(252) -31(1326) // simplified
= -31(1326) +163(252) // swapped sides

But this equals 30 so I am messing up somewhere.
It should equal 2 right? I can't figure out where I got the +28

Unfortunately early in your steps: but rather

Actually, you know, that's a relief because it means the process is probably ok. I thought I was really messing up somewhere.. a miscalculation is GREAT!

Thanks again o_O