The Extended Euclidean Algorithm

Remark 3   Let $r_0 = a, r_1 = b, r_2 = r_0 \ {\rm rem} \ r_1, \ldots$ , $r_{i} = r_{i-2} \ {\rm rem} \ r_{i-1}, \ldots$ , ${\gcd}(a,b) = r_k = r_{k-2} \ {\rm rem} \ r_{k-1}$ be as in Algorithm 1. For $i = 2 \cdots 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

$$\begin{array}{rcl} r_2 & = & r_0 - q_2 \, r_1 \\ r_3 & = & r_... ...s & \vdots \\ r_k & = & r_{k-2} - q_k \, r_{k-1} \\ \end{array}$$ (10)

Observe that each $r_{i}$ writes $s_i \, a + t_i \, b$ . Indeed we have

$$\begin{array}{lclcl} r_0 = s_0 \, a + t_0 \, b & {\rm with} &... ...-1} & {\rm and} & t_k = t_{k-2} - q_k \, t_{k-1} \\ \end{array}$$ (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.

Algorithm 2  

Algorithm 3  

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

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

with coefficients in $R$ . Then, we define

$$R_i = Q_i \cdots Q_1 R_0 \ \ {\rm for} \ \ 1 \leq i \leq k.$$ (13)

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

Proposition 1   With the convention that $r_{k+1} = 0$ and $u_{k+1} = 1$ , for $0 \leq i \leq k$ we have

$(i)$

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

$(ii)$

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

$(iii)$

${\gcd}(a,b) = {\gcd}(r_i, r_{i+1}) = r_k$ ,

$(iv)$

$s_i a + t_i b = r_i$ and $s_{k+1} a + t_{k+1} b = 0$ ,

$(v)$

$s_i t_{i+1} - t_i s_{i+1} = (-1)^i (u_0 \cdots u_{i+1})^{-1}$ ,

$(vi)$

${\gcd}(s_i,t_i) = 1$ ,

$(vii)$

${\gcd}(r_i,t_i) = {\gcd}(a, t_i)$ ,

$(viii)$

the matrices $R_i$ and $Q_i$ are invertible; $Q_i^{-1} = \left( \begin{array}{cc} q_{i+1} & u_{i+1} \\ 1 & 0 \end{array} \right)$ and $R_i^{-1} = (-1)^i (u_0 \cdots u_{i+1}) \left( \begin{array}{cc} t_{i+1} & -t_i \\ - s_{i+1} & s_i \end{array} \right)$ ,

$(ix)$

$a = (-1)^i (u_0 \cdots u_{i+1}) (t_{i+1} r_i - t_i r_{i+1})$ ,

$(x)$

$b = (-1)^{i+1} (u_0 \cdots u_{i+1}) (s_{i+1} r_i - s_i r_{i+1})$ .

Proof. We prove $(i)$ and $(ii)$ by induction on $i$ . The case $i = 0$ follows immediately from the definitions of $s_0, r_0, s_1, r_1$ and $R_0$ . We assume that $(i)$ and $(ii)$ hold for $0 \leq i < k$ . By induction hypothesis, we have

$$\begin{array}{rcl} R_{i+1} \left( \begin{array}{c} a \\ b \en... ...n{array}{c} r_{i+1} \\ r_{i+2} \end{array} \right). \end{array}$$ (14)

Similarly, we have

$$\begin{array}{rcl} R_{i+1} & = & Q_{i+1} R_i \\ & = & Q_{i+1}... ...& t_{i+1} \\ s_{i+2} & t_{i+2} \end{array} \right). \end{array}$$ (15)

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

$$\begin{array}{rcl} s_i t_{i+1} - t_i s_{i+1} & = & {\rm det} ... ... (u_{i+1} \cdots u_2)^{-1} (u_0^{-1} u_1^{-1} - 0). \end{array}$$ (16)

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

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

$${\deg} s_i = {\sum}_{3 \leq j \leq i} {\deg} q_j = n_1 - n_{i-1}$$ (17)

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

$${\deg} t_i = {\sum}_{2 \leq j \leq i} {\deg} q_j = n_0 - n_{i-1}$$ (18)

where $n_i = {\deg} r_i$ for $0 \leq i \leq k$ .

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

$${\deg} s_{i-1} < {\deg} s_i$$ (19)

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

$${\deg} s_i = {\deg} (s_0 - q_2 s_1) = {\deg} (1 - 0 \, q_2 ) = 0 = n_1 - n_{i-1}$$ (20)

and the inequality holds since we have

$$- \infty = {\deg} s_1 < {\deg} s_2 = 0.$$ (21)

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

$${\deg} s_{i-1} < {\deg} s_i < n_{i-1} - n_i + {\deg} s_i = {\deg} q_{i+1} + {\deg} s_i = {\deg} (q_{i+1} s_i)$$ (22)

which implies

$${\deg} s_{i+1} = {\deg} (s_{i-1} - q_{i+1} s_i) = {\deg} (q_{i+1} s_i) > {\deg} s_i$$ (23)

and

$${\deg} s_{i+1} = {deg} q_{i+1} + {\deg} s_i = {deg} q_{i+1} + {\sum}_{3 \leq j \leq i} {\deg} q_j = {\sum}_{3 \leq j \leq i+1} {\deg} q_j$$ (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]$ where ${\bf k}$ is a field. We recall $n = {\deg} a$ . Let $r, s, t \in {\bf k}[x]$ , with $t \neq 0$ , be polynomials such that

$$r = s a + t b \ \ {\rm and} \ \ {\deg} r + {\deg} t < {\deg} a.$$ (25)

Let $j \in \{ 1, \ldots, k + 1 \}$ be such that

$${\deg} r_{j} \leq {\deg} r < {\deg} r_{j-1}.$$ (26)

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

$$r = {\alpha} r_j, s = {\alpha} s_j \ \ {\rm and} \ \ t = {\alpha} t_j.$$ (27)

Proof. First, we observe that the index $j$ exists and is unique. Indeed, we have $- \infty < {\deg} r < n$ and,

$$- \infty = {\deg} r_{k+1} < {\deg} r_k < \cdots < {\deg} r_{i+1} < {\deg} r_{i} < \cdots < {\deg} a = n.$$ (28)

Second, we claim that

$$s_j t = s t_j$$ (29)

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

$$\left( \begin{array}{cc} s_j & t_j \\ s & t \end{array} \right) \... ...\\ g \end{array} \right) = \left( \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$ over the field of fractions of $R$ . Moreover, we know that $\left(\begin{array}{c} f \\ g \end{array}\right) = \left(\begin{array}{c} a \\ b \end{array}\right)$ is the solution. Hence, using Cramer's rule we obtain:

$$a = \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$ while the degree of the right hand side is equal or less than:

$$\begin{array}{rcl} {\deg}(r_j t -r t_j) & \leq & {\max} ({\de... ...n, {\deg} r_{j-1} + n - {\deg} r_{j-1}) \\ & = & n, \end{array}$$ (32)

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

$$t = {\alpha} t_j.$$ (33)

Hence we obtain $s_j {\alpha} t_j = s t_j$ . Since $t \neq 0$ holds, we have $t_j \neq 0$ , leading to

$$s = s_j {\alpha}.$$ (34)

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

Proposition 4   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/2 m\, 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/2 m\, n + {\cal O}(n)$ additions and multiplications in ${\bf k}$ .

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

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

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