The statement of the Extended Euclidean Algorithm

Theorem. (Extended Euclidean Algorithm) Let m and n be positive integers. Define

   a[0] = m,  a[1] = n,

   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,

   x[0] = 1,  x[1] = 0,  y[0] = 0,  y[1] = 1,

   x[k] = x[k-2] - q[k-1] x[k-1]  for  k > 1,

   y[k] = y[k-2] - q[k-1] y[k-1]  for  k > 1.

If a[p] is the last nonzero a[k], then

   a[p] = (m,n) = x[p] m + y[p] n.

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

Before I give the proof, here's a quick overview. The q's compute the greatest common divisor by successive division, i.e. using the standard Euclidean algorithm. Nothing new there! The x's and y's are for bookkeeping; they eventually yield the coefficients in the linear combination.

Proof. I'll take for granted the statement and proof of the standard Euclidean algorithm.

Ignoring the x's and 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 (m,n).

I claim that

   x[k]a[0] + y[k]a[1] = a[k]  for  k > 0.

I'll prove this using induction.

For k = 1, I have

   x[1]a[0] + y[1]a[1] = 0[1] a[0] + 1[1] a[1] = a[1].

Now take k > 1, and assume that the result is true for all indices less than or equal to k. I want to prove the result for k + 1. Compute:

   x[k+1] a[0] + y[k+1] a[1] =

      (x[k-1] - q[k] x[k]) a[0] + (y[k-1] - q[k] y[k]) a[1] =

      (x[k-1] a[0] + y[k-1] a[1]) - q[k] (x[k] a[0] + y[k] a[1]) =
 
      a[k-1] - q[k] a[k] =

      a[k+1].

The first equality comes from the definition of the x's and the y's. I used the induction hypothesis to get the third equality. The last equality uses the definition of the a's.

The result is true for k + 1, so it's true for all k > 0, by induction. In particular, if a[p] = (m,n) is the last nonzero a, then

   x[p] a[0] + y[p] a[1] = a[p] = (m,n).

Send comments about this page to: bikenaga@marauder.millersville.edu.

Last updated: June 13, 2005

Bruce Ikenaga's Home Page

Math Department Home Page

Millersville University Home Page