Greastest Common Divisor question

• Dec 2nd 2012, 08:20 PM
zero312
Greastest Common Divisor question
equation: 111s + 153t = GCD(s,t)

Question Find s and t

I know how to do the problem first go through find the gcd of 111 and 153:
151 = 111 + 42
111 = 42*2 + 27
42 = 27 + 15
15 = 12 + 3
12 = 3*4 + 0

then I have to go back through and solve
42 = 153 - 111
27 = 111 - 42*2
.... etc

But everytime I try and solve it I get an answer that doesn't work, can anyone help me?
• Dec 2nd 2012, 09:17 PM
Re: Greastest Common Divisor question
You can find one solution (s0,t0) using this : Extended Euclidean algorithm - Wikipedia, the free encyclopedia
Then all the solutions are (s0+153k, t0+111k), k in Z.
• Dec 2nd 2012, 10:17 PM
Deveno
Re: Greastest Common Divisor question
you have to keep careful track of signs when "working backwards".

you have a step missing from your gcd calculation, as well:

27 = 15 + 12

you also wrote down 151 instead of 153 in your derivation....little things like that can trip you up.

now we know that:

3 = 15 - 12
12 = 27 - 15
15 = 42 - 27
27 = 111 - (2)(42)
42 = 153 - 111

so, working backwards, we get:

3 = 15 - 12 = (42 - 27) - (27 - 15) we want to keep the 42 and 27, and trade the 15 in for a combination of 42 and 27:

3 = (42 - 27) - (27 - (42 - 27)) = 42 - 27 - 27 + 42 - 27 (see how you need to be careful with the minus signs?)

3 = (2)(42) - (3)(27) (just to be sure we haven't make a mistake yet: (2)(42) = 84, and (3)(27) = 81, and 84 - 81 = 3. cool, we're good so far.)

now we need to "trade up" and express 42 and 27 in terms of "bigger numbers".

since 42 = 153 - 111, and 27 = 111 - (2)(42), we have:

3 = 2(153 - 111) - (3)(111 - 2(42)) = (2)(153) - (2)(111) - (3)(111) + (6)(42), let's collect like terms again before we get confused:

3 = (2)(153) - (5)(111) + (6)(42) <----we still need to express 42 in terms of 151 and 111.

3 = (2)(153) - (5)(111) + (6)(151 - 111) = (2)(153) - (5)(111) + (6)(153) - (6)(111) now collect like terms again:

3 = (8)(153) - (11)(111). so s = -11, and t = 8.

(sanity check: (8)(153) = 1224, and (11)(111) = 1221, and 1224 - 1221 = 3).