The Euclidean Algorithm

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

$$\left\{\vphantom{ \begin{array}{l} c \ \mid \ a \\ c \ \mid \ b \end{array} }\right. \begin{array}{l} c \ \mid \ a \\ c \ \mid \ b \end{array} \iff \left\{\vphantom{ \begin{array}{l} c \ \mid \ b \\ c \ \mid \ r \end{array} }\right. \begin{array}{l} c \ \mid \ b \\ c \ \mid \ r \end{array}$$ (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 r_i $\neq$ 0. From Remark 1 we have

$$\left\{\vphantom{ \begin{array}{l} c \ \mid \ a \\ c \ \mid \ b \end{array} }\right. \begin{array}{l} c \ \mid \ a \\ c \ \mid \ b \end{array} \iff \left\{\vphantom{ \begin{array}{l} c \ \mid \ b \\ c \ \mid \ r_2 \end{array} }\right. \begin{array}{l} c \ \mid \ b \\ c \ \mid \ r_2 \end{array} \iff \iff \left\{\vphantom{ \begin{array}{l} c \ \mid \ r_{k-1} \\ c \ \mid \ r_{k} \end{array} }\right. \begin{array}{l} c \ \mid \ r_{k-1} \\ c \ \mid \ r_{k} \end{array} \iff \left\{\vphantom{ \begin{array}{l} c \ \mid \ r_{k} \\ c \ \mid \ 0 \end{array} }\right. \begin{array}{l} c \ \mid \ r_{k} \\ c \ \mid \ 0 \end{array}$$ (8)

Hence the following properties hold:

• every divisor of a and b divides r_k,
• r_k 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 $\in$ 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(r_k) where r_k 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: % $\longmapsto$ % is the AXIOM function for computing the normal form of an element. Moreover normalizing the intermediate r_i 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