next up previous
Next: The Extended Euclidean Algorithm Up: The Euclidean Algorithm Previous: Euclidean Domains

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

\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 ri $ \neq$ 0. From Remark 1 we have

$\displaystyle \left\{\vphantom{ \begin{array}{l} c \ \mid \ a \\  c \ \mid \ b \end{array} }\right.$$\displaystyle \begin{array}{l} c \ \mid \ a \\  c \ \mid \ b \end{array}$  $\displaystyle \iff$  $\displaystyle \left\{\vphantom{ \begin{array}{l} c \ \mid \ b \\  c \ \mid \ r_2 \end{array} }\right.$$\displaystyle \begin{array}{l} c \ \mid \ b \\  c \ \mid \ r_2 \end{array}$  $\displaystyle \iff$ ... $\displaystyle \iff$  $\displaystyle \left\{\vphantom{ \begin{array}{l} c \ \mid \ r_{k-1} \\  c \ \mid \ r_{k} \end{array} }\right.$$\displaystyle \begin{array}{l} c \ \mid \ r_{k-1} \\  c \ \mid \ r_{k} \end{array}$  $\displaystyle \iff$  $\displaystyle \left\{\vphantom{ \begin{array}{l} c \ \mid \ r_{k} \\  c \ \mid \ 0 \end{array} }\right.$$\displaystyle \begin{array}{l} c \ \mid \ r_{k} \\  c \ \mid \ 0 \end{array}$ (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(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: % $ \longmapsto$ % 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 up previous
Next: The Extended Euclidean Algorithm Up: The Euclidean Algorithm Previous: Euclidean Domains
Marc Moreno Maza
2003-06-06