# Extended Euclidean algorithm

January 28, 2021

Extended Euclidean algorithm for given integers

and computes the integers and such that:Let's observe Bob's notes once again.

gcd(60, 18) | gcd(62, 18) | gcd(65, 18) |
---|---|---|

60 - 3 ⋅ 18 = `6` | 62 - 3 ⋅ 18 = 8 | 65 - 3 ⋅ 18 = 11 |

18 - 3 ⋅ 6 = 0 | 18 - 2 ⋅ 8 = `2` | 18 - 1 ⋅ 11 = 7 |

8 - 4 ⋅ 2 = 0 | 11 - 1 ⋅ 7 = 4 | |

7 - 1 ⋅ 4 = 3 | ||

4 - 1 ⋅ 3 = `1` | ||

3 - 3 ⋅ 1 = 0 |

In each step, you need to subtract the multiplication of the smaller number from the bigger one. Once you get 0, the

can be found in the next to the last line.Thus:

So, how do we calculate

and ?Let's look at the third example above. We need to find integers

and such that:Let's consider the next to the last line:

The integer on the right side presents the

.Thus, we have the integers

and such that:But that's not exactly what we're looking for, right? We need

and , not and .Let's look at the line above the one we just observed:

You can use this line to rewrite

You get:

Now, you have obtained integers

and such that:But that's still not

and ! However, we can use one line above to rewrite this equation to contain and instead of and . Then, we rewrite the equation again to contain and .And that is the whole idea of the extended Euclidean algorithm – going up to the top line where we have

and ! And we finally obtain and such that: