The Euclidean Algorithm

Remark 1   Let a, b $\in$ R mathend000# with b $\neq$ 0 mathend000#. Let r mathend000# be the remainder of a mathend000# w.r.t. b mathend000#. Let c $\in$ R mathend000#. 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 mathend000# means that x mathend000# divides z mathend000#, that is there exists y mathend000# such that xy = z mathend000#.

Algorithm 1  

mathend000#

Let k mathend000# be the greatest value of i mathend000# in Algorithm 1 such that r_i $\neq$ 0 mathend000#. 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 mathend000# and b mathend000# divides r_k mathend000#,
• r_k mathend000# divides a mathend000# and b mathend000#.

Therefore Algorithm 1 computes a gcd of a mathend000# and b mathend000#. 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 mathend000# be an Euclidean domain such for every a $\in$ R mathend000# we can choose a canonical associate denoted by normal(a mathend000#) and called the normal form of a mathend000#. Because of the polynomial case, the unit u mathend000# such that a = u normal(a) mathend000# is denoted lc(a mathend000#) and called the leading coefficient of a mathend000#. Then normal(r_k mathend000#) where r_k mathend000# is the result of Algorithm 1 can be called THE GCD of a mathend000# and b mathend000#. 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$ mathend000# % is the AXIOM function for computing the normal form of an element. Moreover normalizing the intermediate r_i mathend000# 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