Greatest Common Divisor Of Two Polynomials
In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that evenly divides each of the two original polynomials. This concept is analogous to the greatest common divisor of two integers.
In the important case of univariate polynomials over a field the polynomial GCD may be computed, like for the integer GCD, by Euclid's algorithm using long division. The main difference lies in the fact that there is no natural total order on the polynomials. Therefore, "greatest" is meant for the relation of divisibility. As this relation is only a preorder, the polynomial GCD is defined only up to the multiplication by an invertible constant.
The similarity between the integer GCD and the polynomial GCD allows us to extend to univariate polynomials all the properties that may be deduced from Euclid's algorithm and Euclidean division. Moreover, the polynomial GCD has specific properties that make it a fundamental notion in various areas of algebra. Typically, the roots of the GCD of two polynomials are the common roots of the two polynomials, and this allows to get information on the roots without computing them. For example the multiple roots of a polynomial are the roots of the GCD of the polynomial and its derivative, and further GCD computations allow to compute the square-free factorization of the polynomial, which provides polynomials whose roots are the roots of a given multiplicity.
The greatest common divisor may be defined and exists, more generally, for multivariate polynomials over a field or the ring of integers, and also over a unique factorization domain. There exist algorithms to compute them as soon as one has a GCD algorithm in the ring of coefficients. These algorithms proceed by a recursion on the number of variables to reduce the problem to a variant of Euclid's algorithm. They are a fundamental tool in computer algebra, because computer algebra systems use them systematically to simplify fractions. Conversely, most of the modern theory of polynomial GCD has been developed to satisfy the need of efficiency of computer algebra systems.
Read more about Greatest Common Divisor Of Two Polynomials: General Definition, Properties, GCD By Hand Writing Computation, Univariate Polynomials With Coefficients in A Field, GCD Over A Ring and Over Its Field of Fractions, Pseudo-remainder Sequences
Famous quotes containing the words greatest and/or common:
“It is easier for an artful Man, who is not in Love, to persuade his Mistress he has a Passion for her, and to succeed in his Pursuits, than for one who loves with the greatest Violence. True Love hath ten thousand Griefs, Impatiencies and Resentments, that render a Man unamiable in the Eyes of the Person whose Affection he sollicits.”
—Joseph Addison (16721719)
“Do you think that it is possible to have a mere taste of commonness? Either one hates it or makes common cause with it.”
—Franz Grillparzer (17911872)