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
• Purpose
• Recap: the columns in the table of the Euclidean Algorithm
• The extra columns in the table of the Extended Euclidean Algorithm
• Example
• Verify your answers

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?

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:

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.

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

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:

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):

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

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:

• gcd(a, b) = [b on the last row]
• s = [s2 on the last row]
• t = [t2 on the last row]

• gcd(161, 28) = 7
• s = -1
• t = 6

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.

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