Theorem. For all positive integers a and b there exist integers s and t such that
a ⋅ s + b ⋅ t = gcd(a, b).
The proof of this theorem can be found in an exercise in the Rosen textbook. However, the proof merely shows that s and t exist. It doesn't show how to find s and t. The Extended Euclid algorithm can be used to find s and t.
Finding s and t is especially useful when we want to compute multiplicative inverses. Suppose that gcd(a, n) = 1. (That is, a and n are relatively prime.) We have seen that in this situation a has a multiplicative inverse modulo n. That is, there exists an integer, which we call a-1, such that
a ⋅ a-1 ≡ 1 (mod n).Using the theorem above, we can find s and t so that
a ⋅ s + n ⋅ t = 1.Since gcd(a, n) = 1. Now, notice that
a ⋅ s = 1 - n ⋅ t.Now, n ⋅ t ≡ 0 modulo n, so
a ⋅ s ≡ 1 (mod n).Therefore, s ≡ a-1 modulo n and we have found the multiplicative inverse of a.
Now, let's do an example. We let a = 99 and b = 78 and call ExtEuclid(99,78). We use the following table to keep track of recursive calls to ExtEuclid.
| a | b | a div b | d | s | t | |
|---|---|---|---|---|---|---|
| 1 | 99 | 78 | 1 | |||
| 2 | ||||||
| 3 | ||||||
| 4 | ||||||
| 5 | ||||||
| 6 |
Since 78 is not 0, we call ExtEuclid() recursively with parameters 78 and 21 because 99 % 78 is 21. Our table becomes:
| a | b | a div b | d | s | t | |
|---|---|---|---|---|---|---|
| 1 | 99 | 78 | 1 | |||
| 2 | 78 | 21 | 3 | |||
| 3 | ||||||
| 4 | ||||||
| 5 | ||||||
| 6 |
The recursive calls to ExtEuclid continues until we have b == 0. Then ExtEuclid returns the triple (3,1,0) and our table looks like:
| a | b | a div b | d | s | t | |
|---|---|---|---|---|---|---|
| 1 | 99 | 78 | 1 | |||
| 2 | 78 | 21 | 3 | |||
| 3 | 21 | 15 | 1 | |||
| 4 | 15 | 6 | 2 | |||
| 5 | 6 | 3 | 2 | |||
| 6 | 3 | 0 | - | 3 | 1 | 0 |
The 5th call to ExtEuclid now receives the return values from the 6th call and has d1 = 3, s1 = 1 and t1 = 0. Still within the 5th call, we calculate that d = d1 = 3, s = t1 = 0 and
| a | b | a div b | d | s | t | |
|---|---|---|---|---|---|---|
| 1 | 99 | 78 | 1 | |||
| 2 | 78 | 21 | 3 | |||
| 3 | 21 | 15 | 1 | |||
| 4 | 15 | 6 | 2 | |||
| 5 | 6 | 3 | 2 | 3 | 0 | 1 |
| 6 | 3 | 0 | - | 3 | 1 | 0 |
The 4th receives the values d1 = 3, s1 = 0 and t1 = 1 from the 5th call, then computes s = t1 = 1 and
| a | b | a div b | d | s | t | |
|---|---|---|---|---|---|---|
| 1 | 99 | 78 | 1 | |||
| 2 | 78 | 21 | 3 | |||
| 3 | 21 | 15 | 1 | |||
| 4 | 15 | 6 | 2 | 3 | 1 | -2 |
| 5 | 6 | 3 | 2 | 3 | 0 | 1 |
| 6 | 3 | 0 | - | 3 | 1 | 0 |
In the 3rd call, s = -2 and
| a | b | a div b | d | s | t | |
|---|---|---|---|---|---|---|
| 1 | 99 | 78 | 1 | |||
| 2 | 78 | 21 | 3 | |||
| 3 | 21 | 15 | 1 | 3 | -2 | 3 |
| 4 | 15 | 6 | 2 | 3 | 1 | -2 |
| 5 | 6 | 3 | 2 | 3 | 0 | 1 |
| 6 | 3 | 0 | - | 3 | 1 | 0 |
In the 2nd call, s = 3 and
| a | b | a div b | d | s | t | |
|---|---|---|---|---|---|---|
| 1 | 99 | 78 | 1 | |||
| 2 | 78 | 21 | 3 | 3 | 3 | -11 |
| 3 | 21 | 15 | 1 | 3 | -2 | 3 |
| 4 | 15 | 6 | 2 | 3 | 1 | -2 |
| 5 | 6 | 3 | 2 | 3 | 0 | 1 |
| 6 | 3 | 0 | - | 3 | 1 | 0 |
Finally, in the 1st call, s = -11 and
| a | b | a div b | d | s | t | |
|---|---|---|---|---|---|---|
| 1 | 99 | 78 | 1 | 3 | -11 | 14 |
| 2 | 78 | 21 | 3 | 3 | 3 | -11 |
| 3 | 21 | 15 | 1 | 3 | -2 | 3 |
| 4 | 15 | 6 | 2 | 3 | 1 | -2 |
| 5 | 6 | 3 | 2 | 3 | 0 | 1 |
| 6 | 3 | 0 | - | 3 | 1 | 0 |
Now, we can verify that 99 ⋅ (-11) + 78 ⋅ 14 = 3. So, we've found the s and t such that a s + b t = gcd(a,b).
| a | b | a div b | d | s | t | |
|---|---|---|---|---|---|---|
| 1 | 60 | 13 | 4 | 1 | 5 | -23 |
| 2 | 13 | 8 | 1 | 1 | -3 | 5 |
| 3 | 8 | 5 | 1 | 1 | 2 | -3 |
| 4 | 5 | 3 | 1 | 1 | -1 | 2 |
| 5 | 3 | 2 | 1 | 1 | 1 | -1 |
| 6 | 2 | 1 | 2 | 1 | 0 | 1 |
| 7 | 1 | 0 | - | 1 | 1 | 0 |
We can check the final return value is correct: 60 ⋅ 5 + 13 ⋅ (-23) = 300 − 299 = 1. This also shows that 5 is the multiplicative inverse of 60, because (60 * 5) % 13 = 300 % 13 = 1.
to Spring 2009 CMSC 203 Homepage