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:
“The greatest waste of time he knew of was to count the hourswhat good can come of it?and the greatest illusion in the world, to lead ones day by the sound of the clock, and not by precepts of common sense and understanding.”
—François Rabelais (14941553)
“How like a prodigal doth nature seem,
When thou, for all thy gold, so common art!
Thou teachest me to deem
More sacredly of every human heart,
Since each reflects in joy its scanty gleam
Of Heaven, and could some wondrous secret show,
Did we but pay the love we owe,
And with a childs undoubting wisdom look
On all these living pages of Gods book.”
—James Russell Lowell (18191891)