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 \times a + t \times 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 = \text{ the quotient of } a/b$
• $r = \text{ 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 \text{ from the previous row}]$ and $b = [r \text{ 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$, $s2$, $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 \times s2 = 1 - q \times 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 \times 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 \times s2 = 1 - q \times 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 too 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 \times t2$, with the values $t1$, $q$ and $t2$ from the current row.
So $t3 = t1 - q \times t2 = 0 - 5 \times 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.
So we have the following $q$ and $r$: \[ \begin{aligned} q &= [\text{the greatest number below } a, \text{ that's divisible by } b]/b = 21/21 = 1 \\ r &= a - q \times b = 28 - 1 \times 21 = 7 \end{aligned} \] 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 \times s2$ and $t3 = t1 - q \times t2$.
All values in this formulas are the values on the current row. So we have the following $s3$ and $t3$: \[ \begin{aligned} s3 &= s1 - q \times s2 = 0 - 1 \times 1 = -1 \\ t3 &= t1 - q \times t2 = 1 - 1 \times -5 = 1 - -5 = 1 + 5 = 6 \end{aligned} \] 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 \times a + t \times 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 \text{ on the last row}]$
• $s = [s2 \text{ on the last row}]$
• $t = [t2 \text{ 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 \times a + t \times b = gcd(a, b)$,
we can just check whether $s \times a + t \times b$ is indeed equal to $gcd(a, b)$.

But there's a small problem: $s \times a + t \times 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 \times a + t \times 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 \times a + t \times b| = |-1 \times 161 + 6 \times 28| = |-161 + 168| = 7 = gcd(161,28) = gcd(a, b)$
So as you can see, $|s \times a + t \times 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.