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.

Read more about this topic:  Euclidean Algorithm

Famous quotes containing the words structures and/or mathematical:

    It is clear that all verbal structures with meaning are verbal imitations of that elusive psychological and physiological process known as thought, a process stumbling through emotional entanglements, sudden irrational convictions, involuntary gleams of insight, rationalized prejudices, and blocks of panic and inertia, finally to reach a completely incommunicable intuition.
    Northrop Frye (b. 1912)

    An accurate charting of the American woman’s progress through history might look more like a corkscrew tilted slightly to one side, its loops inching closer to the line of freedom with the passage of time—but like a mathematical curve approaching infinity, never touching its goal. . . . Each time, the spiral turns her back just short of the finish line.
    Susan Faludi (20th century)