The Euclidean Algorithm

Remark 1   Let with . Let be the remainder of w.r.t. . Let . It is easy to see that

 (7)

where means that divides , that is there exists such that .

Let be the greatest value of in Algorithm 1 such that . From Remark 1 we have

 (8)

Hence the following properties hold:
• every divisor of and divides ,
• divides and .
Therefore Algorithm 1 computes a gcd of and . However this gcd may not be the nicest one. scale=2.5]
(37) -> a:= (4*x-1/2) * (x+2) * (5*x+1) * (1/20*x+1)

4   883  3   333  2   49
(37)  x  + --- x  + --- x  + -- x - 1
40       8       20

(38) -> b := (4*x-1/2) * (x+4) * (5*x-1) * (1/20*x+1)

4   947  3   2889  2   127
(38)  x  + --- x  + ---- x  - --- x + 2
40       40        5

(39) -> r2 := a rem b

8  3   153  2   557
(39)  - - x  - --- x  + --- x - 3
5       5        20

(40) -> r3 := b rem r2

209  2   33231     209
(40)  --- x  + ----- x - ---
80       640       32

(41) -> r4 := r2 rem r3

(41)  0


Remark 2   Let be an Euclidean domain such for every we can choose a canonical associate denoted by normal( ) and called the normal form of . Because of the polynomial case, the unit such that    normal is denoted lc( ) and called the leading coefficient of . Then normal( ) where is the result of Algorithm 1 can be called THE GCD of and . This leads to the following AXIOM code.
euclideanGcd(a,b) ==
a:=unitCanonical a
b:=unitCanonical b
while not zero? b repeat
(a,b):= (b,a rem b)
b:=unitCanonical b
return a

where unitCanonical: % % is the AXIOM function for computing the normal form of an element. Moreover normalizing the intermediate make computations easier. scale=2.5]
(2) -> a: P := (4*x-1/2) * (x+2) * (5*x+1) * (1/20*x+1)

4   883  3   333  2   49
(2)  x  + --- x  + --- x  + -- x - 1
40       8       20

(3) -> b: P := (4*x-1/2) * (x+4) * (5*x-1) * (1/20*x+1)

4   947  3   2889  2   127
(3)  x  + --- x  + ---- x  - --- x + 2
40       40        5

(4) -> r2 := unitCanonical(a rem b)

3   153  2   557     15
(4)  x  + --- x  - --- x + --
8        32      8

(5) -> r3 := unitCanonical(b rem r2)

2   159     5
(5)  x  + --- x - -
8      2

(6) -> r4 := unitCanonical(r2 rem r3)

(6)  0


Marc Moreno Maza
2008-01-07