Extended Euclidean algorithm

This algorithm extends the Euclidean algorithm to be able to calculate the greatest common divisor of two integers.

Algorithm

extended_euclidean(x,y):
	Input: integers x, y where x >= y >= 0
	Output: integers d, a, b where d = gcd(x,y) and d = xa + yb
1. if y = 0, return (x,1,0)
2. (d, a', b') = extended_euclidean(y,x mod y)
3. return (d, b', a' - floor(x/y)b')

Runtime

Notice this is functionally the same as Euclidean algorithm. So if are -bit integers then this takes .

Correctness

The fact that is correct follows from Euclid’s rule.

We proceed by induction on .

If then and we are done.

Suppose we have it true for all and we want to check it is correct for .

We run extended_euclidean(y,x mod y) lets set mod as we get back correct such that and .

Now write where . Then calculate