The present paper deals with algorithms that, given 
, find
such that
and not
on 
. Therefore the name ``extended Euclidean algorithm'' seems
not to be appropriate... especially when these algorithms are used
outside of an Euclidean ring, to compute something else than a 
.
This paradigm shift, from to has been the fact of Etienne
Bezout (1730-1783), a mathematician known as a textbook writer with
important algebraic researches. His name is attached to the theorem
about intersection of algebraic curves which had a tremendous impact
on the development of algebraic geometry.
Before examining this algorithm in a broader context (convergents, holomorphic functions), let us recall two ``elementary'' utilizations of these Bezout's coefficients: the so called ``Chinese remainder theorem'' and the decomposition of rational functions.
It is well known that the system
(where 
means that 
is exactly
divisible by 
) can be solved as follows : in a first time, you
solve the three systems:
as 
.
If you have no straightforward method to find the 
, and have
to find them by exhaustive trial and error, the cost of the method
is three times the cost of a direct search for . If you have to
solve, like in calendar computations, a lot of equations like Eq. 2
with always the same moduli, the cost of solving the three extra systems
Eq. 3 will be quickly amortized.
But the key point is that Eq. 3 is easy to solve
with Bezout. The algorithm gives numbers such that 
,
leading to the value 
. You obtain 
,
together with 
and 
.
Therefore a solution is 
and all the solutions are given by 
since 
reduces, modulo 
to 
.
An other utilization of Bezout's coefficients is as follows. Let be given a rational fraction whose denominator is factorized, e.g.
, 
and 
.
Bezout gives you such that 
, viz. 
.
Therefore
In this form, the decomposition is not necessarily in lowest terms.
Using again the Euclidean algorithm, we can compute the remainders
and 
and 
.
Since 
is a polynomial and 
, 
the equality
holds. In our example 
.
Substituting 
in the first fraction and 
in the second,
we obtain 
and therefore 
splits into:
In these computations, the step and
can be done in a simpler way after the changing of variables. Substituting
directly into 
, we obtain: 
.
We have too 
,
and we know that polynomial terms do cancel from the degrees
of 
and 
. However, the more difficult part of the whole thing
is the initial factorization of the denominator.
The remainder of this paper is organized as follows : Section 2
deals with the effective computation of the Bezout's coefficients
for ordinary integers. Section 3 deals with computations
inside the ring 
of the polynomials, and gives
some applications. Afterward, Section 4 shows how
to enlarge the results of Section 2 to results concerning
approximations of irrationals by fractions, while Section 5
does the same with holomorphic functions.
