How can the Extended Euclidean Algorithm be simplified for faster computation?

[SirEllwood]

Hi all, ok so below is an example of the Extended Euclidean Algorithm, and i understand the first part perfectly to find the g.c.d.

701 − 2 × 322 = 57,
322 − 5 × 57 = 37,
57 − 37 = 20,
37 − 20 = 17,
20 − 17 = 3,
17 − 5 × 3 = 2,
3 − 2 = 1,

and

1 = 3 − 2
= 6 × 3 − 17
= 6 × 20 − 7 × 17
= 13 × 20 − 7 × 37
= 13 × 57 − 20 × 37
= 113 × 57 − 20 × 322
= 113 × 701 − 246 × 322.

Now on the second part, it is finding the equation of ax +by = 1, which i am generally having to find so i can compute the inverse of a(modb). They have managed to do this in 7 steps. It always takes me like more than twice as many in a really longwinded fashion. Has the example below missed out some steps for the sake of conciseness? I just don't understand how they are doing what they are doing.

For example I would have said

1= 3- 2
1 = (20-17) - (17 - (5x3))
1 = ((57-37) - (37-20)) - ((37-20) - 5(20-17))
etc.

Which is obviously far more longwinded, but equally as methodical. I want to know how to do this more concisely so in an exam it would be far less confusing and time consuming.

Thank you!

 

[dodo]

Hi, "Sir", :P
yes, the second part looks abridged. This is how it would work:

You use the lines in the first part in reverse order, bottom to top. The bottom line says
1 = 3 - 2
(which is a Diophantine equation equal to 1, as required) so you just copy it. Now, each successive line of the first part gives an equation for a number, that you can substitute in the second part. The next one (bottom to top) on the first part says
2 = 17 - 5 x 3
and, substituting in your current Diophantine equation for 1, you get
1 = 3 - 17 + 5 x 3 (and, grouping the terms in 3 together,)
= 6 x 3 - 17
The next equation will give you an equation for 3 in terms of 17 and something else, so you'll be able to substitute, and then group the terms in 17 together. See how it works?

Hope this helps--