Next: Modular Arithmetic Up: The Euclidean Algorithm Previous: The Euclidean Algorithm

## The Extended Euclidean Algorithm

Remark 3   Let r0 = a, r1 = b, r2 = r0 rem r1,..., ri = ri-2 rem ri-1,..., gcd(a, b) = rk = rk-2 rem rk-1 be as in Algorithm 1. For i = 2 ... k let qi be the quotient of ri-2 w.r.t. ri-1 that is

 ri-2  =  qi ri-1 + ri (9)

Hence we have

 r2 = r0 - q2 r1 r3 = r1 - q3 r2 ri = ri-2 - qi ri-1 rk = rk-2 - qk rk-1
(10)

Observe that each ri writes si a + ti b. Indeed we have

 r0 = s0 a + t0 b with s0 = 1 and t0 = 0 r1 = s1 a + t1 b with s1 = 0 and t1 = 1 r2 = s2 a + t2 b with s2 = s0 - q2 s1 and t2 = t0 - q2 t1 r3 = s3 a + t3 b with s3 = s1 - q3 s2 and t3 = t1 - q2 t2 ri = si a + ti b with si = si-2 - qi si-1 and ti = ti-2 - qi ti-1 rk = sk a + tk b with sk = sk-2 - qk sk-1 and tk = tk-2 - qk tk-1
(11)

The elements sk and tk are called the Bézout coefficients of gcd(a, b). 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.

Algorithm 2

Algorithm 3

Proposition 1   Let a, b [x] where is a field. Assume deg(a) = n deg(b) = m.
• Algorithm 3 requires at most m + 2 inversions and 13/2m n + (n) additions and multiplications in .
• If we do not compute the coefficients si, ti then Algorithm 3 requires at most m + 2 inversions and 5/2m n + (n) additions and multiplications in .

Proof. See Theorem 3.11 in [vzGG99].

Proposition 2   Let a, b be multi-precision integers written with m and m words. Algorithm 3 can be performed in (m n) word operations.

Proof. See Theorem 3.13 in [vzGG99].

Next: Modular Arithmetic Up: The Euclidean Algorithm Previous: The Euclidean Algorithm
Marc Moreno Maza
2004-04-27