﻿ The Extended Euclidean Algorithm explained with examples

# Extended Euclidean Algorithm

explained with examples

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.

Purpose
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

ColumnWe use these values on the first row of the tableAnd these values on the other rows
aab from the previous row
bbr from the previous row
qquotient of a/bquotient of a/b
rremainder of a/bremainder of a/b

New, extra columns
ColumnUse these values on the first row of the tableAnd use these values on all other rows
s11s2 from the previous row
s20s3 from the previous row
s3s1 - q × s2 from the current rows1 - 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

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.

Example
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:
abqr
16128521
If you didn't understand this step, go back to the explanation of 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:
abqrs1s2
1612852110
Now we write down the value of s3. Again, we look at the list of extra columns above.
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:
abqrs1s2s3
16128521101
Now we continue with putting the values of t1 and t2 in the table. Since this is the first row, we can use 0 and 1 (as mentioned in the list of extra columns above):
abqrs1s2s3t1t2
1612852110101
Now we calculate t3. Again, we look for the value of t3 in the list of extra columns, substitute the values we already wrote down in the formula of t3 and calculate:
t3 = t1 - q × t2 = 0 - 5 * 1 = -5.
So we put -5 in the table for t3:
abqrs1s2s3t1t2t3
1612852110101-5
Now the first row is done! We continue with the next row.
Again, write down the things you would write down with the Euclidean Algorithm:
abqrs1s2st1t2t3
1612852110101-5
282117
Now we have to find the values of s1 and s2 again. Since this is not the first row anymore, we cannot just write down 1 and 0.
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:
abqrs1s2s3t1t2t3
1612852110101-5
28211701
Now we calculate s3 again. Note that we do not use any values of the previous row, but only of the current row. So:
s3 = s1 - q × s2 = 0 - 1 * 1 = 0 - 1 = -1.
We put it in the table:
abqrs1s2s3t1t2t3
1612852110101-5
28211701-1
Now we find the values of t1 and t2. As mentioned in the list of extra columns:
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:
abqrs1s2s3t1t2t3
1612852110101-5
28211701-11-5
We calculate t3, only with values from the current row:
t3 = t1 - q × t2 = 1 - 1 * -5 = 1 - -5 = 1 + 5 = 6. We put it in the table:
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
2173
0
1-14-56-23
As you can see, r = 0, so we are done.

Results
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]
So in this case, we have found the following:
• 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.

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

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

Multiplicative inverse
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

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

Video