Say we want to find . Then using Euclid's algorithm we have:
So (we knew that anyway). Working backwards systematically we have:
So and . See the proof of Bézout's Identity to see why we can find and this way.
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 . Then using Euclid's algorithm we have:
So (we knew that anyway). Working backwards systematically we have:
So and . See the proof of Bézout's Identity to see why we can find and this way.