1. Euclidean Algorithm

Hey, I am having some trouble with an exercise.
"Illustrate how the Euclidean Algorithm allows you to solve for intergers x, y such that 137x + 1000y = 1. You must show all the steps to demonstrate the use of the Euclidean Algorithm.

Now I understand how to use the Algorithm to find the greatest common factor, but i am not sure what to do for this problem. Anyone have an idea?
Thanks!

2. Say we want to find $\displaystyle \gcd(137, 1000)$. Then using Euclid's algorithm we have:

$\displaystyle 1000 = (7)(137)+41 \Leftrightarrow 137 = (3)(41)+14 \Leftrightarrow 41 = (2)(14)+13 \Leftrightarrow 14 = (1)(13)+1.$

So $\displaystyle \gcd(137, 1000) = 1$ (we knew that anyway). Working backwards systematically we have:

$\displaystyle 1 = 14-1(13) = -41+3(14) = 3(137)-10(41) = 73(137)-10(1000).$

So $\displaystyle x = 73$ and $\displaystyle y = -10$. See the proof of Bézout's Identity to see why we can find $\displaystyle x$ and $\displaystyle y$ this way.

3. that works, thank you =]