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\{ \begin{array}{l} c \ \mid \ a \\ c \ \mid \ b \end{array}... ...f \ \ \left\{ \begin{array}{l} c \ \mid \ b \\ c \ \mid \ r \end{array} \right.$$ (7)

where $x \mid z$ means that $x$ divides $z$ , that is there exists $y$ such that $x y = 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\{ \begin{array}{l} c \ \mid \ a \\ c \ \mid \ b \end{array}... ...\ \left\{ \begin{array}{l} c \ \mid \ r_{k} \\ c \ \mid \ 0 \end{array} \right.$$ (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