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.
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?
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.
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).