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 = 662 - 3 ⋅ 18 = 865 - 3 ⋅ 18 = 11
18 - 3 ⋅ 6 = 018 - 2 ⋅ 8 = 218 - 1 ⋅ 11 = 7
8 - 4 ⋅ 2 = 011 - 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:

The Alice and Bob newsletter

Get highlights of Alice and Bob's adventures delivered to your email box.

Made by XLAB with ❤️
Follow us
Twitter Twitter