The Extended Euclidean Algorithm

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

r_i-2  =  q_i r_i-1 + r_i (9)

Hence we have

r2	=	r0 - q2 r1
r3	=	r1 - q3 r2
$$\vdots$$	$$\vdots$$	$$\vdots$$
ri	=	ri-2 - qi ri-1
$$\vdots$$	$$\vdots$$	$$\vdots$$
rk	=	rk-2 - qk rk-1

(10)

Observe that each r_i mathend000# writes s_i a + t_i b mathend000#. 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
$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$
ri = si a + ti b	with	si = si-2 - qi si-1	and	ti = ti-2 - qi ti-1
$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$
rk = sk a + tk b	with	sk = sk-2 - qk sk-1	and	tk = tk-2 - qk tk-1

(11)

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

mathend000#

Algorithm 3  

mathend000#

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

$$\left(\vphantom{ \begin{array}{cc} s_0 & t_0 \\ s_1 & t_1 \end{array} }\right. \begin{array}{cc} s_0 & t_0 \\ s_1 & t_1 \end{array} \left.\vphantom{ \begin{array}{cc} s_0 & t_0 \\ s_1 & t_1 \end{array} }\right) \left(\vphantom{ \begin{array}{cc} 0 & 1 \\ u^{-1}_{i+1} & - q_{i+1} u^{-1}_{i+1} \end{array} }\right. \begin{array}{cc} 0 & 1 \\ u^{-1}_{i+1} & - q_{i+1} u^{-1}_{i+1} \end{array} \left.\vphantom{ \begin{array}{cc} 0 & 1 \\ u^{-1}_{i+1} & - q_{i+1} u^{-1}_{i+1} \end{array} }\right) \leq \leq$$ (12)

with coefficients in R mathend000#. Then, we define

$$\leq \leq$$ (13)

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

Proposition 1   With the convention that r_k+1 = 0 mathend000# and u_k+1 = 1 mathend000#, for 0 $\leq$ i $\leq$ k mathend000# we have

(i) mathend000#

R_i$\left(\vphantom{ \begin{array}{c} a \\ b \end{array} }\right.$$\begin{array}{c} a \\ b \end{array}$$\left.\vphantom{ \begin{array}{c} a \\ b \end{array} }\right)$ = $\left(\vphantom{ \begin{array}{c} r_i \\ r_{i+1} \end{array} }\right.$$\begin{array}{c} r_i \\ r_{i+1} \end{array}$$\left.\vphantom{ \begin{array}{c} r_i \\ r_{i+1} \end{array} }\right)$ mathend000#,

(ii) mathend000#

R_i = $\left(\vphantom{ \begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array} }\right.$$\begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array}$$\left.\vphantom{ \begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array} }\right)$ mathend000#,

(iii) mathend000#

gcd(a, b) = gcd(r_i, r_i+1) = r_k mathend000#,

(iv) mathend000#

s_ia + t_ib = r_i mathend000# and s_k+1a + t_k+1b = 0 mathend000#,

(v) mathend000#

s_it_i+1 - t_is_i+1 = (- 1)ⁱ(u₀ ^... u_i+1)^-1 mathend000#,

(vi) mathend000#

gcd(s_i, t_i) = 1 mathend000#,

(vii) mathend000#

gcd(r_i, t_i) = gcd(a, t_i) mathend000#,

(viii) mathend000#

the matrices R_i mathend000# and Q_i mathend000# are invertible; Q_i^-1 = $\left(\vphantom{ \begin{array}{cc} q_{i+1} & u_{i+1} \\ 1 & 0 \end{array} }\right.$$\begin{array}{cc} q_{i+1} & u_{i+1} \\ 1 & 0 \end{array}$$\left.\vphantom{ \begin{array}{cc} q_{i+1} & u_{i+1} \\ 1 & 0 \end{array} }\right)$ mathend000# and R_i^-1 = (- 1)ⁱ(u₀ ^... u_i+1)$\left(\vphantom{ \begin{array}{cc} t_{i+1} & -t_i \\ - s_{i+1} & s_i \end{array} }\right.$$\begin{array}{cc} t_{i+1} & -t_i \\ - s_{i+1} & s_i \end{array}$$\left.\vphantom{ \begin{array}{cc} t_{i+1} & -t_i \\ - s_{i+1} & s_i \end{array} }\right)$ mathend000#,

(ix) mathend000#

a = (- 1)ⁱ(u₀ ^... u_i+1)(t_i+1r_i - t_ir_i+1) mathend000#,

(x) mathend000#

b = (- 1)ⁱ⁺¹(u₀ ^... u_i+1)(s_i+1r_i - s_ir_i+1) mathend000#.

Proof. We prove (i) mathend000# and (ii) mathend000# by induction on i mathend000#. The case i = 0 mathend000# follows immediately from the definitions of s₀, r₀, s₁, r₁ mathend000# and R₀ mathend000#. We assume that (i) mathend000# and (ii) mathend000# hold for 0 $\leq$ i < k mathend000#. By induction hypothesis, we have

Ri+1$$\left(\vphantom{ \begin{array}{c} a \\ b \end{array} }\right.$$$$\begin{array}{c} a \\ b \end{array}$$$$\left.\vphantom{ \begin{array}{c} a \\ b \end{array} }\right)$$	=	Qi+1Ri$$\left(\vphantom{ \begin{array}{c} a \\ b \end{array} }\right.$$$$\begin{array}{c} a \\ b \end{array}$$$$\left.\vphantom{ \begin{array}{c} a \\ b \end{array} }\right)$$
	=	Qi+1$$\left(\vphantom{ \begin{array}{c} r_i \\ r_{i+1} \end{array} }\right.$$$$\begin{array}{c} r_i \\ r_{i+1} \end{array}$$$$\left.\vphantom{ \begin{array}{c} r_i \\ r_{i+1} \end{array} }\right)$$
	=	$$\left(\vphantom{ \begin{array}{cc} 0 & 1 \\ u^{-1}_{i+2} & - q_{i+2} u^{-1}_{i+2} \end{array} }\right.$$$$\begin{array}{cc} 0 & 1 \\ u^{-1}_{i+2} & - q_{i+2} u^{-1}_{i+2} \end{array}$$$$\left.\vphantom{ \begin{array}{cc} 0 & 1 \\ u^{-1}_{i+2} & - q_{i+2} u^{-1}_{i+2} \end{array} }\right)$$$$\left(\vphantom{ \begin{array}{c} r_i \\ r_{i+1} \end{array} }\right.$$$$\begin{array}{c} r_i \\ r_{i+1} \end{array}$$$$\left.\vphantom{ \begin{array}{c} r_i \\ r_{i+1} \end{array} }\right)$$
	=	$$\left(\vphantom{ \begin{array}{c} r_{i+1} \\ u^{-1}_{i+2} (r_i - q_{i+2} r_{i+1}) \end{array} }\right.$$$$\begin{array}{c} r_{i+1} \\ u^{-1}_{i+2} (r_i - q_{i+2} r_{i+1}) \end{array}$$$$\left.\vphantom{ \begin{array}{c} r_{i+1} \\ u^{-1}_{i+2} (r_i - q_{i+2} r_{i+1}) \end{array} }\right)$$
	=	$$\left(\vphantom{ \begin{array}{c} r_{i+1} \\ r_{i+2} \end{array} }\right.$$$$\begin{array}{c} r_{i+1} \\ r_{i+2} \end{array}$$$$\left.\vphantom{ \begin{array}{c} r_{i+1} \\ r_{i+2} \end{array} }\right)$$.

(14)

Similarly, we have

Ri+1	=	Qi+1Ri
	=	Qi+1$$\left(\vphantom{ \begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array} }\right.$$$$\begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array}$$$$\left.\vphantom{ \begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array} }\right)$$
	=	$$\left(\vphantom{ \begin{array}{cc} 0 & 1 \\ u^{-1}_{i+2} & - q_{i+2} u^{-1}_{i+2} \end{array} }\right.$$$$\begin{array}{cc} 0 & 1 \\ u^{-1}_{i+2} & - q_{i+2} u^{-1}_{i+2} \end{array}$$$$\left.\vphantom{ \begin{array}{cc} 0 & 1 \\ u^{-1}_{i+2} & - q_{i+2} u^{-1}_{i+2} \end{array} }\right)$$$$\left(\vphantom{ \begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array} }\right.$$$$\begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array}$$$$\left.\vphantom{ \begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array} }\right)$$
	=	$$\left(\vphantom{ \begin{array}{cc} s_{i+1} & t_{i+1} \\ s_{i+2} & t_{i+2} \end{array} }\right.$$$$\begin{array}{cc} s_{i+1} & t_{i+1} \\ s_{i+2} & t_{i+2} \end{array}$$$$\left.\vphantom{ \begin{array}{cc} s_{i+1} & t_{i+1} \\ s_{i+2} & t_{i+2} \end{array} }\right)$$.

(15)

Property (iii) mathend000# follows from our study of Algorithm 1. Claim (iv) mathend000# follows (i) mathend000# and (ii) mathend000#. Taking the determinant of each side of (ii) mathend000# we prove (v) mathend000# as follows:

siti+1 - tisi+1	=	det$$\left(\vphantom{ \begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array} }\right.$$$$\begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array}$$$$\left.\vphantom{ \begin{array}{cc} s_i & t_i \\ s_{i+1} & t_{i+1} \end{array} }\right)$$
	=	detRi
	=	detQi ... detQ1det$$\left(\vphantom{ \begin{array}{cc} s_0 & t_0 \\ s_1 & t_1 \end{array} }\right.$$$$\begin{array}{cc} s_0 & t_0 \\ s_1 & t_1 \end{array}$$$$\left.\vphantom{ \begin{array}{cc} s_0 & t_0 \\ s_1 & t_1 \end{array} }\right)$$
	=	(- 1)i(ui+1 ... u2)-1(u0-1u1-1 - 0).

(16)

Now, we prove (vi) mathend000#. If s_i mathend000# and t_i mathend000# would have a non-invertible common factor, then it would divide s_it_i+1 - t_is_i+1 mathend000#. This contradicts (v) mathend000# and proves (vi) mathend000#. We prove (vii) mathend000#. Let p $\in$ R mathend000# be a divisor of t_i mathend000#. If p | a mathend000#, then p | r_i mathend000# holds since we have r_i = s_ia + t_ib mathend000# from (i) mathend000#. If p | r_i mathend000#, then p | s_ia mathend000# and, thus, p | a mathend000# since t_i mathend000# and s_i mathend000# are relatively prime, from (vi) mathend000#. Therefore, (vii) mathend000# holds. We prove (viii) mathend000#. From (v) mathend000#, we deduce that Q_i mathend000# is invertible. Then, the invertibility of R_i mathend000# follows easily from that of Q_i mathend000#. It is routine to check that the proposed inverses are correct. Finally, claims (ix) mathend000# and (x) mathend000# are derived from (i) mathend000# by multiplying each side with the inverse of R_i mathend000# given in (viii) mathend000#. $\qedsymbol$

In the case R = $\bf k$[x] mathend000# where $\bf k$ mathend000# 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 R = $\bf k$[x] mathend000# where $\bf k$ mathend000# is a field. Then, for 2 $\leq$ i $\leq$ k + 1 mathend000#, we have

$$\sum_{{{3 \leq j \leq i}}}^{{}}$$ (17)

and, for 2 $\leq$ i $\leq$ k + 1 mathend000#, we have

$$\sum_{{{2 \leq j \leq i}}}^{{}}$$ (18)

where n_i = degr_i mathend000# for 0 $\leq$ i $\leq$ k mathend000#.

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

degs_i-1 < degs_i (19)

by induction on 2 $\leq$ i $\leq$ k + 1 mathend000#. For i = 2 mathend000#, the first equality holds since we have

degs_i = deg(s₀ - q₂s₁) = deg(1 - 0 q₂) = 0 = n₁ - n_i-1 (20)

and the inequality holds since we have

$$\infty$$ (21)

Now we consider i $\geq$ 2 mathend000# and we assume that both properties hold for 2 $\leq$ j $\leq$ i mathend000#. Then, by induction hypothesis, we have

degs_i-1 < degs_i < n_i-1 - n_i + degs_i = degq_i+1 + degs_i = deg(q_i+1s_i) (22)

which implies

degs_i+1 = deg(s_i-1 - q_i+1s_i) = deg(q_i+1s_i) > degs_i (23)

and

$$\sum_{{{3 \leq j \leq i}}}^{{}} \sum_{{{3 \leq j \leq i+1}}}^{{}}$$ (24)

where we used the induction hypothesis also. $\qedsymbol$

Proposition 3   With the same notations as in Proposition 1, we assume that R = $\bf k$[x] mathend000# where $\bf k$ mathend000# is a field. We recall n = dega mathend000#. Let r, s, t $\in$ $\bf k$[x] mathend000#, with t $\neq$ 0 mathend000#, be polynomials such that

r = sa + tb  and  degr + degt < dega. (25)

Let j $\in$ {1,..., k + 1} mathend000# be such that

$$\leq$$ (26)

Then, there exists a non-zero $\alpha$ $\in$ $\bf k$[x] mathend000# such that we have

$$\alpha \alpha \alpha$$ (27)

Proof. First, we observe that the index j mathend000# exists and is unique. Indeed, we have - $\infty$ < degr < n mathend000# and,

$$\infty$$ (28)

Second, we claim that

s_jt = st_j (29)

holds. Suppose that the claim is false and consider the following linear system over R mathend000# with $\left(\vphantom{\begin{array}{c} f \\ g \end{array}}\right.$$\begin{array}{c} f \\ g \end{array}$$\left.\vphantom{\begin{array}{c} f \\ g \end{array}}\right)$ mathend000# as unknown:

$$\left(\vphantom{ \begin{array}{cc} s_j & t_j \\ s & t \end{array} }\right. \begin{array}{cc} s_j & t_j \\ s & t \end{array} \left.\vphantom{ \begin{array}{cc} s_j & t_j \\ s & t \end{array} }\right) \left(\vphantom{ \begin{array}{c} f \\ g \end{array} }\right. \begin{array}{c} f \\ g \end{array} \left.\vphantom{ \begin{array}{c} f \\ g \end{array} }\right) \left(\vphantom{ \begin{array}{c} r_j \\ r \end{array} }\right. \begin{array}{c} r_j \\ r \end{array} \left.\vphantom{ \begin{array}{c} r_j \\ r \end{array} }\right)$$ (30)

Since the matrix of this linear system is non-singular, we can solve for f mathend000# over the field of fractions of R mathend000#. Moreover, we know that $\left(\vphantom{\begin{array}{c} f \\ g \end{array}}\right.$$\begin{array}{c} f \\ g \end{array}$$\left.\vphantom{\begin{array}{c} f \\ g \end{array}}\right)$ = $\left(\vphantom{ \begin{array}{c} a \\ b \end{array} }\right.$$\begin{array}{c} a \\ b \end{array}$$\left.\vphantom{ \begin{array}{c} a \\ b \end{array} }\right)$ mathend000# is the solution. Hence, using Cramer's rule we obtain:

$${\frac{{ {\rm det} \left( \begin{array}{cc} r_j & t_j \\ r & t \... ... {\rm det} \left( \begin{array}{cc} s_j & t_j \\ s & t \end{array} \right) }}}$$ (31)

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

deg(rjt - rtj)	$$\leq$$	max(degrj + degt, degr + degtj)
	$$\leq$$	max(degr + degt, degr + n - degrj-1)
	<	max(n, degrj-1 + n - degrj-1)
	=	n,

(32)

by virtue of the definition of j mathend000#, Relation (25) and Proposition 2. This leads to a contradiction. Hence, we have s_jt = st_j mathend000#. This implies that t_j mathend000# divides ts_j mathend000#. Since s_j mathend000# and t_j mathend000# are relatively prime (Point (vi) mathend000# of Proposition 1) we deduce that t_j mathend000# divides t mathend000#. So let $\alpha$ $\in$ $\bf k$[x] mathend000# such that we have

$$\alpha$$ (33)

Hence we obtain s_j$\alpha$t_j = st_j mathend000#. Since t $\neq$ 0 mathend000# holds, we have t_j $\neq$ 0 mathend000#, leading to

$$\alpha$$ (34)

Finally, plugging Equation (33) and Equation (34) in Equation (25), we obtain r = $\alpha$r_j mathend000#, as claimed. $\qedsymbol$

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

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

Proof. See Theorem 3.11 in [GG99]. $\qedsymbol$

Proposition 5   Let a, b $\in$ $\mbox{${\mathbb Z}$}$ mathend000# be multi-precision integers written with m mathend000# and m mathend000# words. Algorithm 3 can be performed in $\cal {O}$(m n) mathend000# word operations.

Proof. See Theorem 3.13 in [GG99]. $\qedsymbol$