The Extended Euclidean Algorithm

Remark 3   Let , , be as in Algorithm 1. For let be the quotient of w.r.t. that is

 (9)

Hence we have

 (10)

Observe that each writes . Indeed we have

 (11)

The elements and are called the Bézout coefficients of . In order to compute a gcd together with its Bézout coefficients Algorithm 1 needs to be transformed as follows. The resulting algorithm (Algorithm 2) is called the Extended Euclidean Algorithm. Finally Algorithm 3 shows how to compute the gcd together with its Bézout coefficients.

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

 (12)

with coefficients in . Then, we define

 (13)

The following proposition collects some invariants of the Extended Euclidean Algorithm.

Proposition 1   With the convention that and , for we have
,
,
,
and ,
,
,
,
the matrices and are invertible; and ,
,
.

Proof. We prove and by induction on . The case follows immediately from the definitions of and . We assume that and hold for . By induction hypothesis, we have

 (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.

Proposition 2   With the same notations as in Proposition 1, we assume that where is a field. Then, for , we have

 (17)

and, for , we have

 (18)

where for .

Proof. We only prove the first equality since the second one can be verified in a similar way. In fact, we prove this first equality together with

 (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.

Proposition 3   With the same notations as in Proposition 1, we assume that where is a field. We recall . Let , with , be polynomials such that

 (25)

Let be such that

 (26)

Then, there exists a non-zero such that we have

 (27)

Proof. First, we observe that the index exists and is unique. Indeed, we have and,

 (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

 (33)

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

 (34)

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

Proposition 4   Let where is a field. Assume .
• Algorithm 3 requires at most inversions and additions and multiplications in .
• If we do not compute the coefficients then Algorithm 3 requires at most inversions and additions and multiplications in .

Proof. See Theorem 3.11 in [GG99].

Proposition 5   Let be multi-precision integers written with and words. Algorithm 3 can be performed in word operations.

Proof. See Theorem 3.13 in [GG99].

Marc Moreno Maza
2008-01-07