# Modified Euclid's Algorithm

1. Oct 29, 2009

### roam

1. The problem statement, all variables and given/known data

Let a = 47 and b = 41. Use the modified euclid's algorithm to find integers x and y such that $$ax+by=1$$.

Here's the solution to this problem:

http://img203.imageshack.us/img203/6044/19152421.gif [Broken]

3. The attempt at a solution

I don't understand how to workout the x and y columns. For example in the fourth row we can see that $$5=-6 \times 47+7 \times 41$$ works, but I don't see how they figured out x=-6 and y=7 in the first place.
I'm revising for my exam and this is not a homework problem, so I appreciate it if anyone could explain to me what's going on here.

Last edited by a moderator: May 4, 2017