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

• Sep 28th 2008, 04:54 PM
cathy1988
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
• Sep 28th 2008, 06:01 PM
o_O
Quote:

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$
• Sep 29th 2008, 11:27 AM
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?
• Sep 29th 2008, 11:31 AM
Jhevon
Quote:

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