Euclid's Extended Algorithm

Date: 09/16/2001 at 23:11:24
From: Anna
Subject: Extended euclid's algorithm

Can you please state for me the steps of Euclid's extended algorithm 
in simple terms? All of the things I have been able to find about it 
on the Internet have just confused me. 

Thank you! 
Anna

Date: 09/17/2001 at 14:08:13
From: Doctor Rob
Subject: Re: Extended euclid's algorithm

Thanks for writing to Ask Dr. Math, Anna.

Start the Euclidean Algorithm as usual, with two positive integers
r(1) and r(2) as input:

   r(1) = q(3)*r(2) + r(3),  0 <= r(3) < r(2),
   r(2) = q(4)*r(3) + r(4),  0 <= r(4) < r(3),
   r(3) = q(5)*r(4) + r(5),  0 <= r(5) < r(4),
   ...

Now notice that the remainders r(3), r(4), r(5), and so on, can be
expressed as combinations of the two input numbers, r(1) and r(2), by
substitution:

   r(3) = 1*r(1) - q(3)*r(2),
   r(4) = 1*r(2) - q(4)*r(3),
        = 1*r(2) - q(4)*[1*r(1) - q(3)*r(2)],
        = -q(4)*r(1) + [1+q(3)*q(4)]*r(2),
   r(5) = 1*r(3) - q(5)*r(4),
        = 1*[1*r(1)-q(3)*r(2)] - q(5)*[-q(4)*r(1)+[1+q(3)*q(4)]*r(2)],
        = [1+q(4)*q(5)]*r(1) - [q(2)+q(4)+q(2)*q(3)*q(4)]*r(2),

and so on.

It turns out that these coefficients of r(1) and r(2) can be computed
right along with the usual Euclidean Algorithm process as follows.
Let a(1) = b(2) = 1, a(2) = b(1) = 0.  Let the a(n)'s and b(n) be
computed recursively from the equations

   a(n+2) = a(n) - q(n+2)*a(n+1),
   b(n+2) = b(n) - q(n+2)*b(n+1).

Then for all n >= 1, you have

   r(n) = a(n)*r(1) + b(n)*r(2).

Example:  Start with the two numbers 114 = r(1) and 48 = r(2).

   114 = 2*48 + 18, so q(3) = 2 and r(3) = 18.
         a(3) = a(1) - q(3)*a(2) = 1 - 2*0 = 1,
         b(3) = b(1) - q(3)*b(2) = 0 - 2*1 = -2.
   48 = 2*18 + 12, so q(4) = 2 and r(4) = 12.
         a(4) = a(2) - q(4)*a(3) = 0 - 2*1 = -2,
         b(4) = b(2) - q(4)*b(3) = 1 - 2*(-2) = 5,
   18 = 1*12 + 6, so q(5) = 1 and r(5) = 6.
         a(5) = a(3) - q(5)*a(4) = 1 - 1*(-2) = 3,
         b(5) = b(3) - q(5)*b(4) = -2 - 1*5 = -7,
   12 = 2*6 + 0, so q(6) = 2 and r(6) = 0.
         a(6) = a(4) - q(6)*a(5) = -2 - 2*3 = -8,
         b(6) = b(4) - q(6)*b(5) = 5 - 2*(-7) = 19.

Sure enough,

   114 =  (1)*114 +  (0)*48,
    48 =  (0)*114 +  (1)*48,
    18 =  (1)*114 + (-2)*48,
    12 = (-2)*114 +  (5)*48,
     6 =  (3)*114 + (-7)*48,
     0 = (-8)*114 + (19)*48.

You can keep track of the work like this

   n      q(n)     r(n)     a(n)     b(n)
   1               114        1        0
   2                48        0        1
   3        2       18        1       -2
   4        2       12       -2        5
   5        1        6        3       -7
   6        2        0       -8       19

Start by filling in the first two rows with r(1) = one of input 
numbers, r(2) = other input number, a(1) = b(2) = 1, a(2) = b(1) = 0.
For each new row labeled n, compute

   q(n) = integer part of r(n-2)/r(n-1),
   r(n) = r(n-2) - q(n)*r(n-1),
   a(n) = a(n-2) - q(n)*a(n-1), and
   b(n) = b(n-2) - q(n)*b(n-1).

Here's a larger example:

   n      q(n)     r(n)     a(n)     b(n)
   1              9810        1        0
   2              7047        0        1
   3         1    2763        1       -1
   4         2    1521       -2        3
   5         1    1242        3       -4
   6         1     279       -5        7
   7         4     126       23      -32
   8         2      27      -51       71
   9         4      18      227     -316
   10        1       9     -278      387
   11        2       0      783    -1090

If you need further explanation, please write again.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/