The Euclidean algorithm is involved in a well-know dilemma in mathematics: "existence" theorems are fine, but you better have a "constructive" one. In other words, a theorem that state for the existence of some object, without giving any means to construct it, is "better than nothing" but rather disappointing.
You can define a principal ring 
by the property that any
ideal 
, i.e. any set verifying 
together with 
,
is the set of the multiples of some 
. In such a case, for
any given 
, it exists a 
such that
, and that relation can be seen as a defining
, the so-called 
of 
and 
(in fact is defined
modulo the equivalence 
, i.e. 
).
But to exhibit such a principal ring is another task if you have not
an explicit algorithm to compute . In fact, the ``top 50''
principal rings are ``Euclidean'', except for 
...
in which a ``quasi-Euclidean'' algorithm allows nevertheless to
work. Historically, Euclid used his algorithm to compute the
of two numbers, for factoring purpose, and to reduce ratios in their
lowest terms. Therefore the existence of 
such that 
was not pointed out at Euclid's time.
The idea that are the key result of the algorithm, and
``only'' a by-product, is a recent one (Bezout, Gauss). This distinction
appears again while programming the algorithm itself. You can go to
and come back to or you can go directly to the Bezout's
coefficients.
A first idea to compute is as follows. Starting from 
and 
, the following steps are iterated. The integer
quotient of 
by 
is computed, i.e. 
and the corresponding remainder 
.
When 
, the first phase is over, and 
.
At that point, we have 
, where
and 
. Let us denote by 
the number of steps
during this phase.
We now put 
and go back to 
by the following steps. Assuming
for some 
, we can
reuse the relation, and
obtain 
.
Therefore 
where 
and 
. A good idea to remember the 
is to put them in a stack, i.e. in a data structure where objects
that are processed in a "last come, first served"
order.
Using 
to create an empty stack, 
to store an
element into the stack and 
to recover a previously stored object,
we obtain Algorithm 1.
The explicit use of a data stack can be avoided with a recursive writing,
leading to Algorithm 2. The program source becomes
shorter, but the algorithm remains the same, and an implicit call
to the system stack is done to store the successive quotients between
their utilization in the first phase to build the next remainder 
and their reutilization in the second phase to build the next pair
.
A more efficient algorithm is Algorithm 3. Often
quoted as ``extended Euclidean algorithm'', this algorithm is
something rather different, and will be better referenced as Bezout's
algorithm. It is to be noticed that this algorithm is often proved
by induction over the number of steps required for the ``true
Euclidean'' algorithm i.e., by the two stage reasoning : to
and back to .
Before to examine the correction of Algorithm 3,
it is worthwhile to mention the superiority of this algorithm over
1 or 2. All of them are 
in time, but the former is 
in space, while the others require
a space to store the 
.
The idea is to consider the very signature of Algorithm 2
as having a worthwhile mathematical meaning, and not only as a ``messy
trick in the sublevels''. Defining 
as 
and accordingly 
as 
, the equation 
can be seen as describing
a linear transform 
in 
, whose matrix is given by 
.
After steps, the algorithm ends with 
where 
. Naming the
elements of 
by 
we obviously have 
together with 
.
Therefore the Euclidean algorithm can be described as storing the
until 
is reached and thereafter computing
from left to right, while the Bezout's algorithm can be described
as computing iteratively, from right to left, without having
to store the . And the same trick can be used as in Gauss-Jordan
elimination: the original column is augmented with a matrix initialized
to the matrix unity. When the column is reduced, the right part of
the enlarged matrix contains the result of the undertaken action,
viz. their product.
And a first result follows: 
is the irreducible expression
of 
. This can be seen from 
. Therefore
, and the Bezout's theorem itself ensure
that 
are coprime.
For teaching purpose, the algorithm can be explicitely written with
matrices, and the whole process can be summarized by Algorithm 4.
We have adopted a ``Maple-like'' syntax, and its flexibility.
To be more precise, 
is a Maple-table, that is emptied by 
.
Such an object grows as required, without constraints on the indices
range, while it's elements are matrices.
Starting with 
and 
, we obtain Figure 1,
that states that:
, while 
.
This algorithm can be accelerated by using ``centered remainders''
i.e. by requiring that 
in 
instead of 
. In a symbolic computing environment,
this is easily done. You define your own 
, and call it, say,
as in Algorithm 5. Thereafter you says subs(iquo
= iquo2, mat_bezout) and the job is done, leading to Figure 2.
It can be shown that the worst case for the ordinary Euclidean is
attained when 
are consecutive in the Fibonacci sequence.
In such a case, we have 
, involving the
golden number 
. The worst case for the centered
algorithm is attained for successive elements of the sequence 
where 
and 
. In such a case 
,
involving 
.
It will be shown in Section 4 that the set of the
obtained during the centered algorithm
is a subset of the set obtained during the ordinary one: accelerating,
but on the same road.
