Next: The Extended Euclidean Algorithm Up: The Euclidean Algorithm Previous: Euclidean Domains

## The Euclidean Algorithm

Remark 1   Let a, b R with b 0. Let r be the remainder of a w.r.t. b. Let c R. It is easy to see that

 (7)

where x | z means that x divides z, that is there exists y such that xy = z.

Algorithm 1

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

 ... (8)

Hence the following properties hold:
• every divisor of a and b divides rk,
• rk divides a and b.
Therefore Algorithm 1 computes a gcd of a and b. 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 R be an Euclidean domain such for every a R we can choose a canonical associate denoted by normal(a) and called the normal form of a. Because of the polynomial case, the unit u such that a = u normal(a) is denoted lc(a) and called the leading coefficient of a. Then normal(rk) where rk is the result of Algorithm 1 can be called THE GCD of a and b. 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 ri 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


Next: The Extended Euclidean Algorithm Up: The Euclidean Algorithm Previous: Euclidean Domains
Marc Moreno Maza
2003-06-06