# The Extended Euclidean Algorithm

Explained step-by-step with examples.

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.

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

#### Purpose

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?

abqr
361036
10614
6412
4220

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

• q = the quotient of a/b
• r = the remainder of a/b
• On the first row a and b were just the a and b that we wanted to know the gcd of, so 36 and 10.
• On all other rows a = [b from the previous row] and b= [r from the previous row]

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?

• When creating the first row in the table, we don't need to calculate s1, s3, t1 and t2.
s1 and t2 are always 1 on the first row and s2 and t1 are always 0 on the first row.
• We also don't need to calculate s3 on the first row, because:
s1 - q × s2 = 1 - q × 0 = 1 - 0 = 1.
So for the first row in the table, we can always write down a 1 for s3. But for all other rows we actually do need to calculate s1 - q × s2.
• Just like we can copy b and r to a and b on the next row,
we can also copy s2 and s3 to s1 and s2 on the next row.
And t2 and t3 to t1 and t2 on the next row.
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.

#### Example

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:

abqr
16128521
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:

abqrs1s2s3t1t2t3
161285

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.

abqrs1s2s3t1t2t3
1612852110101

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:

abqrs1s2s3t1t2t3
1612852110101-5

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
ba
rb
s2s1
s3s2
t2t1
t3t2

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

abqrs1s2s3t1t2t3
1612852110101-5
2821011-5
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.
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:

abqrs1s2s3t1t2t3
1612852110101-5
282117011-5

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:

abqrs1s2s3t1t2t3
1612852110101-5
28211701-11-56

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

abqrs1s2s3t1t2t3
1612852110101-5
28211701-11-56
217301-14-56-23

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

Results

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:

• gcd(a, b) = [b on the last row]
• s = [s2 on the last row]
• t = [t2 on the last row]
So in this case, we have found the following:
• gcd(161, 28) = 7
• s = -1
• t = 6

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)`.

Example

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:

abqrs1s2s3t1t2t3
1612852110101-5
28211701-11-56
217301-14-56-23
70-14-6-23
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
150--10-01-

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.

#### Calculator

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!

#### Video

For those who like to hear someone explain it instead of having to read a lot.