Euclidean Algorithm

**fenderic** · September 29th 2010, 04:16 PM

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!

**TheCoffeeMachine** · September 30th 2010, 01:13 AM

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.

**fenderic** · September 30th 2010, 10:46 AM

that works, thank you =]

Thread: Euclidean Algorithm

LinkBack

Thread Tools

Display