# 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

rk = rk−2qk rk−1

where each remainder is strictly smaller than its predecessor, |rk| < |rk−1|. Second, the size of each remainder has a strict lower limit, such as |rk| ≥ 0. Third, there is only a finite number of sizes smaller than a given remainder |rk|. 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 g1, g2, 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 mkgk

where s, t and mk 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 qkgk

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