# Number Theory GCD Linear Combination

• Jul 13th 2008, 05:33 PM
mander
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!) (Worried)

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 (Headbang)
• Jul 13th 2008, 05:48 PM
o_O
Unfortunately early in your steps: \$\displaystyle 252 \neq 3(66) + 58\$ but rather \$\displaystyle 252 = 3(66) + 54\$
• Jul 14th 2008, 12:08 AM
mander
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! (Itwasntme)

Thanks again o_O :)