Remark 3Let
r0 = a, r1 = b, r2 = r0remr1,...,
ri = ri-2remri-1,...,
gcd(a, b) = rk = rk-2remrk-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 = qiri-1 + ri
(9)
Hence we have
r2
=
r0 - q2r1
r3
=
r1 - q3r2
ri
=
ri-2 - qiri-1
rk
=
rk-2 - qkrk-1
(10)
Observe that each ri writes
sia + tib.
Indeed we have
r0 = s0a + t0b
with
s0 = 1
and
t0 = 0
r1 = s1a + t1b
with
s1 = 0
and
t1 = 1
r2 = s2a + t2b
with
s2 = s0 - q2s1
and
t2 = t0 - q2t1
r3 = s3a + t3b
with
s3 = s1 - q3s2
and
t3 = t1 - q2t2
ri = sia + tib
with
si = si-2 - qisi-1
and
ti = ti-2 - qiti-1
rk = ska + tkb
with
sk = sk-2 - qksk-1
and
tk = tk-2 - qktk-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.