Extended Euclidean Algorithmexplained with examples
Before you read this page
This page assumes that you have read the explanation about the Euclidean Algorithm (click here), the non-extended version of the algorithm. If you have not read that page, please consider reading it. It is not very complicated, but if you skip it, this page will become more difficult to understand.
Instead of reading that page, you could watch a video (click) about it.
You can also watch a video instead of reading this entire page. That video is at the bottom of this page.
The Extended Euclidean Algorithm
There are many version of this algorithm, but they all compute the same thing.
For example, there are versions that use backwards substitution. Luckily, our version is not that complicated.
Basically, it's the same as the Euclidean Algorithm, but with some extra columns.
So you can see this algorithm as an extension of the Euclidean Algorithm, hence its name: Extended Euclidean Algorithm.
Assume you know the two variables a and b.
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.
List of columns we are going to use in the new table
Columns we already had
|Column||We use these values on the first row of the table||And these values on the other rows|
|a||a||b from the previous row|
|b||b||r from the previous row|
|q||quotient of a/b||quotient of a/b|
|r||remainder of a/b||remainder of a/b|
New, extra columns
|Column||Use these values on the first row of the table||And use these values on all other rows|
|s1||1||s2 from the previous row|
|s2||0||s3 from the previous row|
|s3||s1 - q × s2 from the current row||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|
In the calculations below, we will refer to the table above as list of extra columns.
If you find these tables confusing or have no idea what they mean, don't worry. Just look at the example below in which we explain how it works.
a = 161 and b = 28. Calculate gcd(a, b) and s and t.
We begin with writing down the things that we also write down in the Euclidean Algorithm:
Now we write down the values of s1 and s2. This is very simple, because this is still the first row.
If you look in the list of extra columns above, you can see that, for the first row, s1=1 and s2=0.
So we can just write down 1 and 0:
This is still the first row, so s3 = s1 - q × s2.
The s1, q and s2 values in this formula are all values we already wrote down in this row, so we can substitute these values in the formula of s3. So we can compute:
s3 = s1 - q × s2 = 1 - 5 × 0 = 1 - 0 = 1.
Now we know that s3 = 1, so we put it in the table:
t3 = t1 - q × t2 = 0 - 5 * 1 = -5.
So we put -5 in the table for t3:
Again, write down the things you would write down with the Euclidean Algorithm:
As mentioned in the list of extra columns, the value of s1 in each row not being the first row is just the same as s2 in the previous row.
s2 was 0 in the previous row, so now s1 becomes 0.
s2 in this row equals the value of s3 in the previous row. s3 was 1 in the previous row, so s2 = 1 in this row. Now we put them in the table:
s3 = s1 - q × s2 = 0 - 1 * 1 = 0 - 1 = -1.
We put it in the table:
t1 = the value of t2 in the previous row = 1
t2 = the value of t3 in the previous row = -5
We put them in the table:
t3 = t1 - q × t2 = 1 - 1 * -5 = 1 - -5 = 1 + 5 = 6. We put it in the table:
The final answers of the calculation are always these:
- gcd(161, 28) = [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
Let's verify these answer by checking whether s × a + t × b = gcd(a, b).
s × a + t × b = -1 × 161 + 6 * 28 = -161 + 168 = 7.
gcd(161, 28) = 7
So yes! They are both 7, which means they are equal. Our calculation is correct.
When you use the algorithm with negative numbers (i.e. a is negative, b is negative or both a and b are negative),
the verification might not be correct. For example, if you take a=1013 and b=-778, you get s=-341 and t=-444.
Then s × a + t × b = -341 × 1013 + -444 × -778 = -1. This is not equal to gcd(1013, -778) = 1. This is because of the property of the gcd that it cannot be a negative number. To solve this problem, you have to tweak things a bit. For instance, you could take the absolute value of s × a + t × b:
|s × a + t × b| = |-341 × 1013 + -444 × -778| = |-1| = 1.
Now it is equal to the gcd of 1013 and -778.
1) In this example, we often referred to the "list of extra columns". You should know that, although the values inside that list are real, the list itself is not really a thing. When you are learning the Extended Euclidean Algorithm, you can use this list, but don't take it too seriously. Practice until you know the values from the list, but don't learn the list itself.
2) Calculating s3 on the first row is not necessary.
On the first row we have s3 = s1 - q × s2 where s1,q,s2 are also values from the first row. If you look at the list of extra columns, you see that s1 = 1 and s2 = 0 on the first row. So s3 = 1 - q × 0 = 1 - 0 = 1.
So you don't actually have to calculate s3 on the first row of the table, since it always equals 1.
If you are interested in using the Extended Euclidean Algorithm to calculate a multiplicative inverse modulo something, then go on to the next page:
Calculate multiplicative inverse using the Extended Euclidean Algorithm
These calculations can be a lot of work, so why don't you consider using our calculator (click).
Also useful to verify that your calculations are correct.
VideoIt is probably quicker to read this page if you want to learn about the Euclidean Algorithm.
But if you still prefer watching a video instead (or if you want to understand it better), you can watch the video below.
The video covers the same material as the rest of this page, so if you've already read this page and you think you understand it, then there is no need for watching this video.
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