Symbolic Computing

LT20, 4:00-6:00pm
Wed, 19 March 2003

Extended Euclidean Algorithm

Another theorem with regarding to GCD gives us away to compute inverse in (Subscript[Z, p]) or other field.

Let D be a Euclidean domain and let a, b ∈ D (not both zero).  Then there exists elements s, t ∈ D such that

GCD(a, b)  =  s a  +  t b

This theorem says GCD of a and b is a linear combination of a and b.  For example.
GCD(18,30) = 6.  We have
6  =  s 18  +  t 30,  with s  =  2, t  =  -1. 

Let b be a prime number p, and |a| < p,  then
GCD(a,  p)  =  1  =  
          s a  +  t b.    Modulo p we get
1 mod p   =  (s a  +  t p) mod p
or  1  =  s a  mod p
Thus s is the multiplicative inverse in the field ((Subscript[Z, p]);*,+).

Extended Euclidean algorithm is like Euclidean algorithm, with few more book-keeping.

(* Return {GCD[a, b],  s,  t} such that GCD[a, b]  =  
        s*a  +  
          t*b. 
*) 
ExtendedEuclidean[a_, b_]  :=  
        Module[{c, c1, c2, d, d1, d2, r, r1, 
            r2}, 
{c, c1, c2}  =  {a, 1,  
              0};  
{d, d1, d2}  =  {b,  0,  
              1}; 
While[ 
            d ≠  0, 
q  =  
              quotient[c, d]; 
r  =  
              c  -  q*d; 
r1  =  
              c1  -  q*d1; 
r2  =  
              c2  -  q*d2; 
{c, c1, c2}  =  {d, d1,  
                d2}; 
{d, d1, d2}  =  {r,   r1, 
                r2}
]; 
s =  
            c1; 
t = c2; 
{c,  s,  
            t}
];

 (* The definition of quotient[] depends on the algberaic structure of the integral domain .   For integer Z,  
      we have built - 
        in function. *) 
quotient[a_,  b_]  :=  Quotient[a, b]

Again, the extended Euclidean algorithm works for all Euclidean domains when the quotient[ ] function is properly defined.

Here is the working of algorithm to input a = 18, b = 30.

Iteration      q     c    c1    c2      d     d1    d2
     0             -    18    1     0       30    0       1   ( a  & b)
     1            0     30   0     1       18     1      0   (c gets d, d gets r)
     2            1     18   1     0       12    -1     1 
     3            1     12  -1     1        6     2     -1
     4            2      6    2    -1       0     -5      3   (stop when d = 0)

Example:Compute the inverse of 4 in (Subscript[Z, 5]),using extended Euclidean algorithm .  GCD (4, 5) = 
          1,running the algorithm we find s = -1,t = 1 ,so (4^(-1)) = \(\(-1\)\ mod\ 5\  = \ \(4. \ \ This\ is\ checked\ because\ 4*4\ mod\ 5\  = \ 1. \)\)

ExtendedEuclidean[4, 5]

Why the extended Euclidean algorithm works?

The key to understand extended Euclidean algorithm is to note that it is always true that c = a*(Subscript[c, 1]) + b*(Subscript[c, 2]), i.e., this is a loop invariant.    Before the loop starts, we have for this equation,
a = 1*a + 0 b.  At the end of the run, we have GCD[a,b] = a*s + b*t.    

To show that extended Euclidean algorithm works, we just need to show that 
c = a*(Subscript[c, 1]) + b*(Subscript[c, 2])                                                                    (1)
d = a*(Subscript[d, 1]) + b*(Subscript[d, 2])                                                                   (2)
is valid before and after each update.

Show that it is also true that 
r = a*(Subscript[c, 1]) + b*(Subscript[c, 2]).                                                     (3)

Because equations (1), (2), and (3) is true in every iteration, it is true through out.

An example of polynomial GCD over field Q.

Let  a(x)  =  
        48 (x^3) - 84  (x^2) + 42  x - 36, 
b(
          x)  =  -4 (x^3) - 10  (x^2) + 44  x  -  30. 
compute GCD[a(x),  b(x)], s(x) and t(x).

Following the extended Euclidean algorithm step by step, we first begin with 
c(x)  =  a(x),  (Subscript[c, 1])(x)  =  
          1,  (Subscript[c, 2])(x)  =  0;
d (x)  =  b (x), (Subscript[d, 1])(x) = 0, (Subscript[d, 2]) (x)  =  1. 
We compute r(x)  =  Mod[a(x),  b(x)] and quotient q(x) by a long division.
                                               -12   \(TraditionalForm\`\(\(\ \ \ \ \ \ \ \ \ \)\(\(⟵\)\(\ \ \)\(q(x)\)\)\)\)
-4 (x^3) - 10  (x^2) + 
        44  x - 30  (Sqrt[48  (x^3)   -   84 
                   (x^(2  )) +   42  
                  x   -   36]) 
                                             48 (x^3)   +  120 (x^2)  - 528  x  + 360
                                            __________________________
                           r(x) ⟶                -204 (x^(2   )) + 570  x  - 
        396

Thus, after first iteration, we have  (replace c by d, replace d by r = c - q*d)
c(x)  =  b(x), (Subscript[c, 1])(x)  =  0, (Subscript[c, 2])(x) = 1; 
d (x)  =  r (x)  =  -204 (x^2) + 
                570  x  - 396, (Subscript[d, 1])(x) =(Subscript[r, 1])(x) = 1
(Subscript[d, 2]) (x) =(Subscript[r, 2])(x)=0-(-12)*1= 12

Now we are in the second iteration, and do a long division of c(x) by d(x), similar to above, we obtain have
                                          (4/204) x       +  (4320/(204^2))
\(TraditionalForm\`\(-204\) x\^2 + 570  x - 
        396\ \ \@\(\(\ \ \ \)\(\(-4\) x\^\(\(3\)\(\ \ \)\)\  - \ \ \ 10  x\^2\ \ \  + \ \ \ 44  x\ \ \  - \ \ \ 30\)\)\)
                                           -4 (x^3)  + (2280/204) (x^2) - (1584/204) 
          x
                                           ____________________________
                                                 -(4320/204) (x^2)   + (10560/204) 
          x     -  30
-(4320/204) (x^2) + (2462400/(204^2)) x - 
        (1710720/(204^2))
                                                  ________________________
                                                                 -(308160/(204^2)) x  + (462240/204)
Reduce to lowest terms for the fraction with GCD computation over integer, we find
q(x) = (1/51) x +(30/289),
r(x)  =  -(2140/289) x  + (3210/289)
Thus new values for c,  (Subscript[c, 1]),  (Subscript[c, 2]) are
c(x) = -204 (x^2) + 570  x  - 396,
(Subscript[c, 1])(x) = 0, (Subscript[c, 2])(x)  =  1. 
d(
          x)  =  r(x)  = -(2140/289) x  + 
            (3210/289), 
(Subscript[d, 1])(
          x)  =   - q(x)  =  -(1/51) x  - 
            (30/289), 
(Subscript[d, 2])(x)  =  
        1 -  q(x)*12

The third and also the last iteration we do
-(2140/289) x  + (3210/289)  \(TraditionalForm\`\@\(\(\(-204\) x\^2\)\(+\)\(570  x\)\(\ \)\(+\)\(396\)\(\ \ \)\)\)
and find 
q(x)  = (14739/535) x - (19074/535),   r(
          x)  =  0

Thus GCD(a, b)  =  c(x) = -(2140/289) x  + (3210/289),
(Subscript[c, 1])(x) = s(x) = -(1/51) x  - (30/289),
(Subscript[c, 2])(
          x)  =  t(
            x)  = - (12/51) 
              x -(71/289)

Note that the fractions gets bigger and bigger during iterations.  The computation is simpler in a finite field, e.g., in ((Subscript[Z, p]); +, *).

Nonuniqueness of GCD

If c is the greatest common divisor in an integral domain D, so is any  u *c for any member u such that (u^(-1))exists.  Such members are called units.  Since if c|a and c | b,  (u*c) | a is the same as c | (u^(-1)) a.  In Z (the set of integers), only -1 and 1 have inverse, so if c is a GCD, so is -c.   In Q[x] (the set of polynomials with rational coefficients),  all zeroth-order polynomial a(x)  =  (Subscript[a, 0]) for (Subscript[a, 0]) ≠  0  is a unit.  So all GCDs are related by a multiplicative constants.

GCD of Polynomial over Z

GCD of polynomial over Z is complicated as Z[x] is not an Euclidean domain, thus Euclidean algorithm cannot be applied. This is because the division property
a = b*q + r
does not hold for Z[x].    But a similar property known as pseudo-division allows GCD to be computed within Z[x].

Some Applications of GCD

GCD computation is one of the basic computation in a symbolic algebraic system.  GCD computation is required for:
	1. simplifying polynomial rational functions;
	2. factor of polynomials;
	3. symbolic integration of polynomial rational functions;
	4. inverse of extension fields.

An example of GCD over (Subscript[Z, p])

Modulo arithmetic

If a, b, c,  d ∈ Z, we have the following properties regarding operations modulo p. These show the relation between the integral domain (Z;+,*) and field ((Subscript[Z, p]); +,*).  Note that each element in Z is mapped to (Subscript[Z, p]) by taking the modulo p.

0.	(a + b) mod p  =  (a mod p  +  
              b mod p)  mod p
\(TraditionalForm\`\((a*
              b)\)\ mod\ p\  = \ \((\((a\ mod\ p)\)\ *\ \((b\ mod)\)\ p\ )\)\ mod\ p\)

1.	a  =  b mod p   implies   a - b is a multiple of p.

2.	If a  =  b mod p, and c =  d mod p, then
	a  +  c  =  
        b  +  d mod p, 
a*c  =  b*d mod p
	
3.	a * x  =  b mod p  has solution  x  =  (a^(-1))*b mod p,  where (a^(-1)) is the multiplicative inverse in the field (Subscript[Z, p]).

Note that in Z there is no inverse for an integer except -1 and 1.  
The relation between Z and (Subscript[Z, p]) is known as a ring morphism.

Consider again the polynomials above:
a(x)  =  
        48 (x^3) - 84  (x^2) + 42  x - 36, 
b(
          x)  =  -4 (x^3) - 10  (x^2) + 44  x  -  30. 

Assuming that the integers and variable x live in (Subscript[Z, p]), we have (after modulo by 5 of the coefficients)
a(x)  =  
        3  (x^3) + (x^2) + 2  x + 4, 
b(x)  =  
        (x^3) + 4  x.

A long division would like this:
                                3
            \(TraditionalForm\`x\^3 + 
        4  x\ \ \ \ \@\(3  x\^\(\(3\)\(\ \ \ \)\) + \ \ \ x\^\(\(2\)\(\ \ \ \)\) + \ \ \ 2\ x\ \ \ \ \  + \ \ \ \ 4\)\)
                               3  (x^3)  +  0  (x^2)    +   2  x
                               ______________________
                                            \(TraditionalForm\`\(\(\ \ \)\(x\^2\ \ \  + \ \ \ \ 0\ \ \ \ \  + \ \ \ \ 4\)\)\)
One more division
                                   x
                  \(TraditionalForm\`x\^2 + 
        4\ \ \ \@\(x\^3\ \  + \ \ \ \ 0\ x\^2\ \ \  + \ \ \ 4\ x\ \ \ \ \  + \ \ \ 0\)\)
\(TraditionalForm\`\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^3\ \ \ \  + \ \ 0\ x\^2\ \ \ \  + \ \ \ 4\ x\)
                                ________________________
                                                                             0
Thus GCD(a(x),b(x)) in (Subscript[Z, 5])[x] is (x^2) + 4, which is quite different from the results in Q[x].