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
- Recap: the columns in the table of the Euclidean Algorithm
- The extra columns in the table of the Extended Euclidean Algorithm
- 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.
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
Let's say we want to know the values of
t such that:
s × a + t × b = gcd(a, b)
(This is called the Bézout identity, where
t are the Bézout coefficients.)
The Euclidean Algorithm can calculate
With the Extended Euclidean Algorithm, we can not only calculate
gcd(a, b), but also
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:
|Column||Value on the first row||Value on other rows|
|a||the input a||b from the previous row|
|b||the input b||r from the previous row|
|q||quotient of a/b||quotient of a/b|
|r||remainder of a/b||remainder 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.
|Column||Value on the first row||Value on other rows|
|s1||1||s2 from the previous row|
|s2||0||s3 from the previous row|
|s3||s1 - q × s2 from the current row = 1||s1 - q × s2 from the current row|
|t1||0||t2 from the previous row|
|t2||1||t3 form the previous row|
|t3||t1 - q × t2 from the current row||t1 - q × t2 from the current row|
- 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.
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):
|Copy this value from the previous row||And put it in this column on the current row|
If you do this, then the table looks like this:
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.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]
- 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
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
|s × a + t × b| = gcd(a, b)
with s=s2, t=t2 and gcd(a, b)=b on the last row (where r=0)
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) =
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.
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:
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:
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:
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
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!
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: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