E.E.A. .com
It doesn't have to be difficult if someone just explains it right.

The Extended Euclidean Algorithm

Explained step-by-step with examples.

Before you read this page

Make sure that you have read the page about the Euclidean Algorithm (or watch the video instead). That page explains how to construct a table using the Euclidean Algorithm. In the Extended Euclidean Algorithm we're going to do the same, but with some extra columns in the table. So if you have no idea what we're talking about, this page is going to be confusing, while it really doesn't have to be. Just read that page about the Euclidean Algorithm first. Please

Text or video?

You can choose to read this page or watch the video at the bottom of this page. Both cover the same material, so there's no need to look at both. Reading this page might be quicker, but the video could feel a little more detailed.

Table of contents:

Versions of the Extended Euclidean Algorithm

There are many versions of the Extended Euclidean Algorithm. You may have seen some already that require things like backwards substition or to write "gcd(...,...)=" over and over again while you're not really sure what you're doing. In our version, we don't need that kind of nonsense. We write down everything we need and skip all the things we don't need to write down. A table is perfect for this. We have already seen how to construct a table using the Euclidean algorithm, so now we're just going to add more columns.


Why do we need more columns if the Euclidean Algorithm can already calculate the gcd? Why do we need the Extended Euclidean Algorithm at all?
Well, because it allows us to calculate some extra things.

Assume you know the two variables a and b.
Let's say we want to know the values of s and t such that:
s × a + t × b = gcd(a, b)
(This is called the Bézout identity, where s and t are the Bézout coefficients.)
The Euclidean Algorithm can calculate gcd(a, b).
With the Extended Euclidean Algorithm, we can not only calculate gcd(a, b), but also s and t.
That is what the extra columns are for.

Recap: the columns in the table of the Euclidean Algorithm

Remember when we were calculating the gcd of 36 (=a) and 10 (=b) with the Euclidean algorithm? Remember what the table looked like?


The table had 4 columns: a, b, q and r.

We can summarize this in an overview as follows:

ColumnValue on the first rowValue on other rows
athe input ab from the previous row
bthe input br from the previous row
qquotient of a/bquotient of a/b
rremainder of a/bremainder of a/b

The extra columns in the table of the Extended Euclidean Algorithm

In the Extended Euclidean Algorithm, we have all of the columns from the Euclidean Algorithm.
We also have some extra columns: s1, s2, s3, t1, t2 and t3.
What do we need to put in those columns? Have a look at this overview.

Overview of extra columns

ColumnValue on the first rowValue on other rows
s11s2 from the previous row
s20s3 from the previous row
s3s1 - q × s2 from the current row = 1s1 - q × s2 from the current row
t10t2 from the previous row
t21t3 form the previous row
t3t1 - q × t2 from the current rowt1 - q × t2 from the current row

So what do we see here?

Does all of this sound confusing to you? Don't worry, just have a look at the example below where we're going to guide you through the algorithm step by step.


a = 161 and b = 28. Calculate gcd(a, b) and s and t.

We begin with writing down the things that we would also write down in the Euclidean Algorithm:

If you didn't understand this step, go back to the explanation of the Euclidean Algorithm.

The Extended Euclidean algorithm uses extra columns, so we're going to add them to the right:


As you can see in the overview of extra columns, some of the values we have to put on the first row are already known.
On the first row, the following is always the case: s1=1, s2=0, t1=0 and t2=1.
Usually we need to calculate s3, but not on the first row, since s3 = s1 - q × s2 = 1 - q × 0 = 1. So s3 is always 1 on the first row.
Now let's add these values to the table.


Next time when you create the first row, don't think to much. Just add 1 0 1 0 1 to the table after you wrote down the value of r.
Then the only thing left to do on the first row is calculating t3.
We look again at the overview of extra columns and we see that (on the first row) t3 = t1 - q × t2, with the values t1, q and t2 from the current row.
So t3 = t1 - q × t2 = 0 - 5 × 1 = -5. Let's add this value to the table to finish the first row:


Now the first row is done! We continue with the next row.
Let's start with copying some values from the previous row to this row. What values can we copy?
(This follows from the overview of columns in the Euclidean Algorithm and the overview of extra columns):

Copy this value from the previous rowAnd put it in this column on the current row

If you do this, then the table looks like this:

Here we have included colors to make it clear which values have been copied and where we put them.
Once you understand this, just ignore the colors. When you are creating a table, you don't have to color your own table. Unless you want to of course ;)

So now we only have to calculate q, r, s3 and t3 on this row.
Let's start with q and r.
First, we're looking for the greatest number below a, that's divisible by b.
On this row we have a=28 and b=21, so what's the biggest number below 28 that we can divide by 21? Yes, it's actually 21 itself.
q = [the greatest number below a, that's divisible by b]/b = 21/21 = 1
r = a - q × b = 28 - 1 × 21 = 7
If you find this confusing, look at the explanation of how to calculate q and r on the page of the Euclidean Algorithm.
Now let's add the values to the table:


From overview of extra columns we know that s3 = s1 - q × s2 and t3 = t1 - q × t2.
All values in this formulas are the values on the current row. So:
s3 = s1 - q × s2 = 0 - 1 × 1 = -1 and
t3 = t1 - q × t2 = 1 - 1 × -5 = 1 - -5 = 1 + 5 = 6
If we add these values to the table, we get:


Now we calculate the next row the same way, such that we get:


As you can see, r = 0, so we are done! Now let's have a look at what we've actually calculated.


Now, remember that we're calculating the value of s, t and gcd(a, b) in this equation:
s × a + t × b = gcd(a, b)
Since we have reached r=0, we are done and we can now find the answers in the last row of the table:

So in this case, we have found the following:

Verify your answers

Executing the Extended Euclidean algorithm involves a lot of steps, so small mistakes are easily made.
Luckily we can check whether we have done it correctly.
Since we we're trying to find s, t and gcd(a, b) such that s × a + t × b = gcd(a, b),
we can just check whether s × a + t × b is indeed equal to gcd(a, b).
But there's a small problem: s × a + t × b can result in a negative number (e.g. if we use a negative a or b), while the gcd of two numbers is always positive.
In that case they are not equal, even though the calculation was correct. To so solve this, we can cheat a little bit:
we take the absolute value of s × a + t × b and compare that to the gcd(a, b).


In our earlier example, we used the Extended Euclidean algorithm on a=161 and b=28.
We found that s=-1, t=6 and gcd(161,28)=7.
So if we put these numbers in the formula, we get:
|s × a + t × b|= |-1 × 161 + 6 × 28| = |-161 + 168| = 7 = gcd(161,28) = gcd(a, b)
So as you can see, |s × a + t × b| is indeed equal to gcd(a, b). So our calculation is correct.

What if b=0?

Then the gcd(a,b)=|a|, s=1 and t=0.

The gcd

Remember the property of the gcd that gcd(a,0)=|a|. That's why gcd(a,b)=|a| when b=0.

Why is s=1 and t=0?

We mentioned before that when r=0, you could add another row. If we do that with the earlier example, the table looks like this:

This is exactly the same table as we saw before, but with an extra row.
In this extra row, b from the previous row has been copied into a again, r into b, s2 into s1, s3 into s2, t2 into t1 and t3 into t2.
So the answer now appears at two places: in the column of b where r=0 and in the column of a on the last row. The answer of s can now also be found in two places: column s2 on the row where r=0 and column s1 on the last row. Likewise, t can be found in column t2 (where r=0) and t1 (last row). This makes sense, because you can now see why a in the last row is the answer: b=0 and gcd(a,0)=|a|.
This extra row is actually part of the Extended Euclidean Algorithm, but we usually decide to skip it, since we can already tell the answers once we reach r=0.

But when b already equals 0 at the start, this extra row is actually the only row in the table. So if we decide to omit it, we have a table with no rows. This is what happens when you run our calculator.
Let's say a=15 and b=0. This is how the calculator displays the output:

abqr s1s2s3 t1t2t3
So as you can see, there are no rows.
If we wouldn't skip the extra row in our version of the Extended Euclidean algorithm and we run it again with a=15 and b=0, the table would look like this:
abqr s1s2s3 t1t2t3

So here the "extra" row in the table is the only row in the table.
Which means that the answers we are looking for have already been shifted to the left. As if they have been copied from the previous row where r=0, although that row doesn't exist in this case.
So the answers that we are looking for can be found in the following columns again:

  • gcd(a,b) in column a
  • s in column s1
  • t in column t1
Remember that in the first row we always have s1=1 and t1=0. Since this is the only row (whenever b=0 from the start), this is also the first row. That's why when b=0, we always have gcd(a,b)=|a|, s=1 and t=0.


Do you want to see more examples? Do you want to practice more? Or are you just very lazy?
Then check out our awesome calculator that can do this entire calculation of the Extended Euclidean algorithm for you!
It shows all intermediate steps in the table, the final answers and also the verification of the answers.
→ Go the calculator now!

Multiplicative inverse

Interested to see how we can use the Extended Euclidean algorithm to calculate a multiplicative inverse? Check this page!


For those who like to hear someone explain it instead of having to read a lot.
This video covers the same material as this page, so you don't have to watch it if you already read this page
Unless you feel like you need to understand it better.

0:00 Introduction
0:28 What is the Extended Euclidean Algorithm and what can we calculate with it?
1:18 Showing the differences between the algorithms by converting a table from the Euclidean Algorithm to the Extended Euclidean Algorithm
7:23 The table that lists all columns and their values: don't take it too seriously
8:50 Another example: using the Extended Euclidean algorithm to find gcd(a,b), s and t
12:30 The online calculator for the Extended Euclidean Algorithm
12:59 Thank you for watching, have a look at the description