# Euclidean Algorithm

• Sep 29th 2010, 04: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, 01:13 AM
TheCoffeeMachine
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.
• Sep 30th 2010, 10:46 AM
fenderic
that works, thank you =]