
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!

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 = 141(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.
