# Thread: Euclidean Algorithm--can't seem to make it work backwards

1. ## Euclidean Algorithm--can't seem to make it work backwards

I'm working a problem in my textbook and am stuck. Here's what I have so far:
GCD (34, 58)
58 = 34 x 1 + 24
34 = 24 x 1 + 10
24 = 10 x 2 + 4
10 = 4 x 2 + 2 = GCD (4, 2)

So working backwards:

2 = 10 - 4 x 2
= 10 - (24 - 10 x 2) x 2
= 10 x 2 - 24 + 10 x 2
= 10 x 4 - 24
= (34 - 24) x 4 - 24

And that's where I get lost. I work it through and cannot seem to get the right answer. I know that I need to get 12 to go with a and 7 to go with b, but how do I express this going backwards using the algorithm? There must be some mistake I'm making. Thanks in advance

2. Originally Posted by cathy1988
So working backwards:

2 = 10 - 4 x 2
= 10 - (24 - 10 x 2) x 2
= 10 x 2 - 24 + 10 x 2 What happened here??
= 10 x 4 - 24
= (34 - 24) x 4 - 24
(In red)

$10 - \left[24 - 2(10)\right](2) \ = \ 10 - 24(2) + 4(10) \ = \ 5(10) - 2(24) = \hdots$

3. OK, my professor obviously never explained how to handle these tougher algorithms. So using what you've given me, I now have:

2 = 10(5) - 24(2)

And I'm lost. Which of these do I substitute (34-24) into? Is it 10 x 5 or 24 x 2 or both?

4. Originally Posted by cathy1988
OK, my professor obviously never explained how to handle these tougher algorithms. So using what you've given me, I now have:

2 = 10(5) - 24(2)

And I'm lost. Which of these do I substitute (34-24) into? Is it 10 x 5 or 24 x 2 or both?
you want a combination of 2 and 4, so if there is a 2, leave it, anything but 2 or 4 you change

see post #8 here