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

$\displaystyle \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  

\fbox{
\begin{minipage}{10 cm}
\begin{description}
\item[{\bf Input:}] $a,b \in ...
...\> \> $i$\ := $i+1$\ \\
\> {\bf return} $r_{i-2}$
\end{tabbing}\end{minipage}}

Let $ k$ be the greatest value of $ i$ in Algorithm 1 such that $ r_i \neq 0$ . From Remark 1 we have

$\displaystyle \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: 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

Marc Moreno Maza
2008-01-07