(9) |

(10) |

(11) |

**In order to analyze Algorithms 2 and 3
we introduce the following matrices
**

(12) |

(13) |

- ,
- ,
- ,
- and ,
- ,
- ,
- ,
- the matrices and are invertible; and ,
- ,
- .

(14) |

Similarly, we have

(15) |

Property follows from our study of Algorithm 1. Claim follows and . Taking the determinant of each side of we prove as follows:

(16) |

Now, we prove . If and would have a non-invertible common factor, then it would divide . This contradicts and proves . We prove . Let be a divisor of . If , then holds since we have from . If , then and, thus, since and are relatively prime, from . Therefore, holds. We prove . From , we deduce that is invertible. Then, the invertibility of follows easily from that of . It is routine to check that the proposed inverses are correct. Finally, claims and are derived from by multiplying each side with the inverse of given in .

**In the case
where
is a field,
the following Proposition 2
shows that the degrees of
the Bézout coefficients of the
Extended Euclidean Algorithm grow linearly
whereas Proposition 3
shows that Bézout coefficients are essentially unique,
provided that their degrees are small enough.
**

(17) |

(18) |

(19) |

by induction on . For , the first equality holds since we have

(20) |

and the inequality holds since we have

(21) |

Now we consider and we assume that both properties hold for . Then, by induction hypothesis, we have

(22) |

which implies

(23) |

and

(24) |

where we used the induction hypothesis also.

(26) |

(27) |

(28) |

Second, we claim that

(29) |

holds. Suppose that the claim is false and consider the following linear system over with as unknown:

(30) |

Since the matrix of this linear system is non-singular, we can solve for over the field of fractions of . Moreover, we know that is the solution. Hence, using Cramer's rule we obtain:

(31) |

The degree of the left hand side is while the degree of the right hand side is equal or less than:

(32) |

by virtue of the definition of , Relation (25) and Proposition 2. This leads to a contradiction. Hence, we have . This implies that divides . Since and are relatively prime (Point of Proposition 1) we deduce that divides . So let such that we have

Hence we obtain . Since holds, we have , leading to

Finally, plugging Equation (33) and Equation (34) in Equation (25), we obtain , as claimed.

*
*

2008-01-07