Greatest common denominator

Question

My problem is figuring out how to express the GCD as a linear combination of $(9,11)$. So far, I have:

$$11 = 9 + 2$$ $$9 = 4 \cdot 2 + 1$$

From here, I'm not sure if I put $2 = 2 \cdot 1$

As for "working backwards", I think I start out with $1 = 9 - 4\cdot 2= 9 - 4(11 - 9)$ maybe?

I'm drawing blanks trying to solve this.

Sorry for the garbage formatting. – John Hunter Nov 08 '13 at 04:41 — John Hunter, Nov 08 '13 at 04:41
You're right. $gcd(9,11)=1=9-4(11-9)=5\cdot9-4\cdot11$ – Henry Nov 08 '13 at 04:50 — Henry, Nov 08 '13 at 04:50

score 0 · Answer 1 · answered Nov 08 '13 at 04:51

0

The key to "working backwards" in these problems is NOT multiplying things out. From the last equation, we get $$1=9-4\cdot 2$$ Then we see that $2$ can be written in terms of multiples of $11$ and $9$ using equation 1. So we get $$1=9-4\cdot 2=9-4(11-9)=5\cdot 9 -4\cdot 11$$

answered Nov 08 '13 at 04:51

D Wiggles

2,818

How did you go from 9-4(11-9) to 59-411? – John Hunter Nov 08 '13 at 04:55
I distributed the 4 through the parentheses, then combined "like" multiples of 4. $9-4(11-9)=9-4\cdot 11+4\cdot 9=5\cdot 9-4\cdot 11$. – D Wiggles Nov 08 '13 at 05:33

Greatest common denominator

1 Answers1