next up previous
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
$\displaystyle \vdots$ $\displaystyle \vdots$ $\displaystyle \vdots$
ri = ri-2 - qi ri-1
$\displaystyle \vdots$ $\displaystyle \vdots$ $\displaystyle \vdots$
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
$\displaystyle \vdots$ $\displaystyle \vdots$ $\displaystyle \vdots$ $\displaystyle \vdots$ $\displaystyle \vdots$
ri = si a + ti b with si = si-2 - qi si-1 and ti = ti-2 - qi ti-1
$\displaystyle \vdots$ $\displaystyle \vdots$ $\displaystyle \vdots$ $\displaystyle \vdots$ $\displaystyle \vdots$
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  

\fbox{
\begin{minipage}{10 cm}
\begin{description}
\item[{\bf Input:}] $a,b \in ...
...\
\> {\bf return}($r_{i-2}, s_{i-2}, t_{i-2}$) \\
\end{tabbing}\end{minipage}}

Algorithm 3  

\fbox{
\begin{minipage}{11 cm}
\begin{description}
\item[{\bf Input:}] $a,b \in ...
...\
\> {\bf return}($r_{i-2}, s_{i-2}, t_{i-2}$) \\
\end{tabbing}\end{minipage}}

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

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

Proposition 2   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 [vzGG99]. $ \qedsymbol$


next up previous
Next: Modular Arithmetic Up: The Euclidean Algorithm Previous: The Euclidean Algorithm
Marc Moreno Maza
2003-06-06