The Extended Euclidean Algorithm says that the greatest common divisor of two numbers can be expressed as a linear combination of the two numbers. There are various ways of obtaining such a linear combination. The algorithm given below is from a paper by S. P. Glasby [1]. It involves half as many computations as the usual forward recurrence!
Theorem. (Extended Euclidean Algorithm) Let a and b be positive integers. Define
a[0] = a, a[1] = b, q[k] = Floor (a[k-1]/a[k]) for k > 0, a[k] = a[k-2] - a[k-1] q[k-1] for k > 1,
Suppose that a[n] is the last nonzero a[k]. Define y[n] = 0 and y[n - 1] = 1. Then taking k equal to the numbers from n - 2 down to 1 in that order, define:
y[k - 1] = q[k] y[k] + y[k + 1].
Then
a[n] = (a,b) = (-1)^n y[1] a + (-1)^(n+1) y[0] b.
(The Floor of a real number x is the greatest integer less than or equal to x. So Floor(1.5) = 1, Floor(-2.1) = -3, and Floor(0) = 0.)
Don't be alarmed by all the subscripts! Believe it or not, the algorithm isn't bad for hand computation if you're careful to arrange the numbers in a table.
Proof. I'll take for granted the statement and proof of the standard Euclidean algorithm.
Ignoring the y's, the computation of the a's and q's is the same as the computation of the standard Euclidean algorithm: The a's are the remainders, and the q's are the quotients. Thus, the algorithm terminates, and when it does, the last nonzero a is the greatest common divisor (a,b).
Note that (a,b) is only defined if at least one of a, b is nonzero. If a is nonzero, then (a,0) = a and a = (1)(a) + (0)(0). This proves the result if one of the numbers is 0, so I may as well assume both are nonzero. Moreover, since (a,b) = (|a|,|b|), I can assume both numbers are positive.
With the a's, q's, and y's defined as in the statement of the theorem, I claim that for k = 1, ..., n,
(-1)^(n+k+1) a[k - 1] y[k] + (-1)^(n+k) a[k] y[k - 1] = a[n].
I will prove this by downward induction, starting with k = n and working downward to k = 1.
For k = n, I have
(-1)^(2n+1) a[n - 1] y[n] + (-1)^(2n) a[n] y[n - 1] =
-a[n - 1] y[n] + a[n] y[n - 1] =
(-a[n - 1])(0) + (a[n])(1) = a[n].
The result holds for k = n.
Next, suppose 1 < k < n. Suppose the result holds for k + 1, i.e.
(-1)^(n+k+2) a[k] y[k + 1] + (-1)^(n+k+1) a[k + 1] y[k] = a[n].
I want to prove the result for k. Substitute y[k + 1] = y[k - 1] - q[k] y[k] in the preceding equation and simplify:
a[n] = (-1)^(n+k+2) a[k] y[k + 1] + (-1)^(n+k+1) a[k + 1] y[k] =
(-1)^(n+k+2) a[k](y[k - 1] - q[k] y[k]) +
(-1)^(n+k+1) a[k + 1] y[k] =
(-1)^(n+k) a[k](y[k - 1] - q[k] y[k]) +
(-1)^(n+k+1) a[k + 1] y[k] =
(-1)^(n+k) a[k] y[k - 1] + (-1)^(n+k+1) a[k] q[k] y[k] +
(-1)^(n+k+1) a[k + 1] y[k] =
(-1)^(n+k) a[k] y[k - 1] + (a[k] q[k] +
a[k + 1])(-1)^(n+k+1) y[k] =
(-1)^(n+k) a[k] y[k - 1] + (-1)^(n+k+1) a[k - 1] y[k].
This proves the result for k, so the result holds for all k from 1 to n, by downward induction.
In particular, for k = 1, the result says
a[n] = (-1)^(n+1) a[1] y[0] + (-1)^(n+2) a[0] y[1] =
(-1)^(n+1) a[1] y[0] + (-1)^n a[0] y[1] =
(-1)^n y[1] a[0] + (-1)^(n+1) y[0] a[1].
[1] S. P. Glasby, Extended Euclid's algorithm via backward recurrence relations, Mathematics Magazine, 72(3)(1999), 228--230.
Send comments about this page to: bikenaga@marauder.millersville.edu.
Last updated: June 13, 2005
Millersville University Home Page
Copyright 1998 by Bruce Ikenaga