# Euclidean Algorithm

• Sep 29th 2010, 05:16 PM
fenderic
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!
• Sep 30th 2010, 02:13 AM
TheCoffeeMachine
Say we want to find $\gcd(137, 1000)$. Then using Euclid's algorithm we have:

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

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

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

So $x = 73$ and $y = -10$. See the proof of Bézout's Identity to see why we can find $x$ and $y$ this way.
• Sep 30th 2010, 11:46 AM
fenderic
that works, thank you =]