Thread: Extended Euclidean Algorithm

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 dont 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!

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 dont 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.

For the most part, I think these problems are just plain tedious! Books just tend to leave out all of the "longwinded" dirty work just so that it looks nice in print.

Your method looks like it works just fine, but as you continue on, it can get pretty messy. I just worked out this problem in 14 lines. When I do it, I simplify as much as I can before I move on to the next step, so that I don't lose track of where I am; and it saves from having to do all of the simplifying at the end. Heres how I do it:

1 = 3 + (-1)2
= 3 + (-1)[17 + (-3)5]
= (-1)17 + 6(3) simplified
= (-1)17 + 6[20 + (-1)17] next step
= (6)20 + (-7)17 simplified
= (6)20 + (-7)[37 + (-1)20] next step
= (-7)37 + (13)20 .
. .
. .
.
= (-20)322 + (113)[701 + (-2)322]
= (113)701 + (-246)322

On exams, I would have a spot on the paper where I put the "concise 7-step" part and on the side or on scratch paper I would have all of the dirtywork of simplifying. That definitely makes things look neater for the grader.

It just takes some practice to get used to the Euclidean Method.

Oh, and if you think that this is such a messy longwinded method of doing this, just wait, you'll probably have to do the Euclidean Method with polynomials instead of integers one of these days!