Euclidean Algorithm - Generalizations To Other Mathematical Structures

Generalizations To Other Mathematical Structures

The Euclidean algorithm has three general features that together ensure it will not continue indefinitely. First, it can be written as a sequence of recursive equations

r_k = r_k−2 − q_k r_k−1

where each remainder is strictly smaller than its predecessor, |r_k| < |r_k−1|. Second, the size of each remainder has a strict lower limit, such as |r_k| ≥ 0. Third, there is only a finite number of sizes smaller than a given remainder |r_k|. Generalizations of Euclid's algorithm with these basic features have been applied to other mathematical structures, such as tangles and transfinite ordinal numbers.

An important generalization of the Euclidean algorithm is the concept of a Gröbner basis in algebraic geometry. As shown above, the GCD g of two integers a and b is the generator of their ideal. In other words, for any choice of the integers s and t, there is another integer m such that

sa + tb = mg.

Although this remains true when s, t, m, a and b represent polynomials of a single variable, it is not true for rings of more than one variable. In that case, a finite set of generator polynomials g₁, g₂, etc. can be defined such that any linear combination of two multivariable polynomials a and b can be expressed as multiples of the generators

sa + tb = Σ_k m_kg_k

where s, t and m_k are multivariable polynomials. Any such multivariable polynomial f can be expressed as such a sum of generator polynomials plus a unique remainder polynomial r, sometimes called the normal form of polynomial f

f = r + Σ_k q_kg_k

although the quotient polynomials q_k may not be unique. The set of these generator polynomials is known as a Gröbner basis.