This

algorithm not only finds the

gcd of two

integers it also finds the

modular inverses (a.k.a.

multiplicative inverse) of those numbers. If

gcd(a, b)=1, then we know there exists a

^{-1}(mod b) and b

^{-1}(mod a). In other words a

^{-1}*a≡1(mod b), or a

^{-1}*a mod b=1.

Finding a multiplicative inverse is very important in some cryptographic systems. Like the Hill Cipher.

Extended Euclidean algorithm is really the same as the Euclidean Algorithm except instead of using mod we use division to find the quotient and calculate the remainder. This and a few side calculations allow us to not only find the greatest common divisor of a and b, but also their modular inverses. Extended Euclidean algorithm uses the equation a*u + b*v=1. This will only be true when u is the modular inverse of a(mod b) and v is the modular inverse of b(mod a). But it is not always true that we can find these modular inverses they only exist when gcd(a,b) is equal to 1. But even when they don't exist we can still use the algorithm to find the gcd, because that 1 is really the just a remainder. So the equation we rely on is really a*u + b*v = r.

Finding the quotient, q, instead of just the remainder allows us to use the quotient to caluculate auxillary numbers u and v. Where u_{i} = u_{i-2} - u_{i-1}*q_{i-2} (mod a) and v_{i} = v_{i-2} - v_{i-1}*q_{i-2} (mod b). Now you just run through normal Euclid's Algorithm finding the remainder, r_{i}, using the quotient, q_{i}=int(a_{i}/b_{i}), instead of a_{i} mod b_{i}. Starting with i=0. But since u and v are calculated from previous values we can't caluculate them until i=2. So when a < b for i=0, we set u_{0}=0 and v_{0}=1, for i=1, we set u_{1}=1 and v_{1}=0. We pick these numbers so that for i=0, r = a, and for i=1, r = b, using the a*u + b*v = r equation. Reverse this for a > b.

For some this may be easier to understand given psuedocode. Here is some that performs the Extend Euclidian Algorithm, egcd(a, b). (u, v, r) and (U, V, R) are used to keep the calculations of past values and makes the algorithm more memory effient than the hand written method because you don't need to keep so much history of the auxillary numbers.

**Step 1:**
- if a < b then
- Set u=0, v=1, and r=b
- Set U=1, V=0, and R=a
- else
- Set u=1, v=0, and r=a
- Set U=0, V=1, and R=b

**Step 2:**
if R = 0 then return r (for the gcd) and no inverses exist.
if R = 1 then return R (for the gcd), V (for the inverse a(mod b)) and U (for the inverse of b(mod a)).
**Step 3:**
Calculate q = int(r/R)
Calculate t1 = u - U*q
Calculate t2 = v - V*q
Calculate t3 = r - R*q
set u=U, v=V, r=R
set U=t1, V=t2, R=t3
goto Step 2.

Note: throughout the algorithm the following relationships hold
b*t1 + a*t2 = t3
b*u + a*v = r
b*U + a*V = R
You can also combine this algorithm with the

binary method to increase its efficiency, called the

Extended Binary Euclidean Algorithm. (

*I would node that, but I haven't been able to figure out how the implementation I've seen works*) Suggested reading:

Euclid's Algorithm,

greatest common divisor, and

Binary GCD algorithm.

Here is a java implementation:

public int[] extEuclid(int a, int b) {
if (b == 0) {
int result[] = {1, 0, a};
return result;
}
int u = a;
int v = b;
int x1, x2, x3, y1, y2, y3;
if (u < v) {
x1 = 0; x2 = 1; x3 = v;
y1 = 1; y2 = 0; y3 = u;
} else {
x1 = 1; x2 = 0; x3 = u;
y1 = 0; y2 = 1; y3 = v;
}
while (y3 > 1) {
int q = (int) (x3/y3);
int t1 = x1 - q*y1;
int t2 = x2 - q*y2;
int t3 = x3 - q*y3;
x1 = y1; x2 = y2; x3 = y3;
y1 = t1; y2 = t2; y3 = t3;
}
if (y3 == 0) {
int result[] = {x1, x2, x3};
return result;
} else {
int result[] = {y1, y2, y3};
return result;
}
}