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:
“Can we not teach children, even as we protect them from victimization, that for them to become victimizers constitutes the greatest peril of all, specifically the sacrificephysical or psychologicalof the well-being of other people? And that destroying the life or safety of other people, through teasing, bullying, hitting or otherwise, putting them down, is as destructive to themselves as to their victims.”
—Lewis P. Lipsitt (20th century)
“Art and ideology often interact on each other; but the plain fact is that both spring from a common source. Both draw on human experience to explain mankind to itself; both attempt, in very different ways, to assemble coherence from seemingly unrelated phenomena; both stand guard for us against chaos.”
—Kenneth Tynan (19271980)