The Extended Euclidean Algorithm

Remark 3 Let r₀ = a, r₁ = b, r₂ = r₀ rem r₁,..., r_i = r_i-2 rem r_i-1,..., gcd(a, b) = r_k = r_k-2 rem r_k-1 be as in Algorithm 1. For i = 2^...k let q_i be the quotient of r_i-2 w.r.t. r_i-1 that is

r_i-2 = q_i r_i-1 + r_i

(9)

Hence we have

r₂	=	r₀ - q₂ r₁
r₃	=	r₁ - q₃ r₂
$\displaystyle \vdots$	$\displaystyle \vdots$	$\displaystyle \vdots$
r_i	=	r_i-2 - q_i r_i-1
$\displaystyle \vdots$	$\displaystyle \vdots$	$\displaystyle \vdots$
r_k	=	r_k-2 - q_k r_k-1

(10)

Observe that each r_i writes s_i a + t_i b. Indeed we have

r₀ = s₀ a + t₀ b	with	s₀ = 1	and	t₀ = 0
r₁ = s₁ a + t₁ b	with	s₁ = 0	and	t₁ = 1
r₂ = s₂ a + t₂ b	with	s₂ = s₀ - q₂ s₁	and	t₂ = t₀ - q₂ t₁
r₃ = s₃ a + t₃ b	with	s₃ = s₁ - q₃ s₂	and	t₃ = t₁ - q₂ t₂
$\displaystyle \vdots$	$\displaystyle \vdots$	$\displaystyle \vdots$	$\displaystyle \vdots$	$\displaystyle \vdots$
r_i = s_i a + t_i b	with	s_i = s_i-2 - q_i s_i-1	and	t_i = t_i-2 - q_i t_i-1
$\displaystyle \vdots$	$\displaystyle \vdots$	$\displaystyle \vdots$	$\displaystyle \vdots$	$\displaystyle \vdots$
r_k = s_k a + t_k b	with	s_k = s_k-2 - q_k s_k-1	and	t_k = t_k-2 - q_k t_k-1

(11)

The elements s_k and t_k 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.

Proposition 1 Let a, b $\in$ $\bf k$ [x] where $\bf k$ is a field. Assume deg(a) = n $\geq$ deg(b) = m.

Algorithm 3 requires at most m + 2 inversions and 13/2m n + $\cal {O}$ (n) additions and multiplications in $\bf k$ .
If we do not compute the coefficients s_i, t_i then Algorithm 3 requires at most m + 2 inversions and 5/2m n + $\cal {O}$ (n) additions and multiplications in $\bf k$ .