General Definition
Let p and q be polynomials with coefficients in an integral domain F, typically a field or the integers. A greatest common divisor of p and q is a polynomial d that divides p and q and such that every common divisor of p and q also divides d. Every pair of polynomials has a GCD if and only if F is a unique factorization domain.
If F is a field and p and q are not both zero, d is a greatest common divisor if and only if it divides both p and q and it has the greatest degree among the polynomials having this property. If p = q = 0, the GCD is 0. However, some authors consider that it is not defined in this case.
The greatest common divisor of p and q is usually denoted "gcd(p, q)".
The greatest common divisor is not unique: if d is a GCD of p and q, then the polynomial f is another GCD if and only if there is an invertible element u of F such that
and
- .
In other words, the GCD is unique up to the multiplication by an invertible constant.
In the case of the integers, this indetermination has been settled by choosing, as the GCD, the unique one which is positive (there is another one, which is its opposite). With this convention, the GCD of two integers is also the greatest (for the usual ordering) common divisor. When one want to settle this indetermination in the polynomial case, one lacks of a natural total order. Therefore, one chooses once for all a particular GCD that is then called the greatest common divisor. For univariate polynomials over a field, this is usually the unique GCD which is monic (that is has 1 as coefficient of the highest degree). In more general cases, there is no general convention and above indetermination is usually kept. Therefore equalities like d = gcd(p, q) or gcd(p, q) = gcd(r, s) are usual abuses of notation which should be read "d is a GCD of p and q" and "p, q has the same set of GCD as r, s". In particular, gcd(p, q) = 1 means that the invertible constants are the only common divisors, and thus that p and q are coprime.
Read more about this topic: Greatest Common Divisor Of Two Polynomials
Famous quotes containing the words general definition, general and/or definition:
“The following general definition of an animal: a system of different organic molecules that have combined with one another, under the impulsion of a sensation similar to an obtuse and muffled sense of touch given to them by the creator of matter as a whole, until each one of them has found the most suitable position for its shape and comfort.”
—Denis Diderot (1713–1784)
“In communist society, where nobody has one exclusive sphere of activity but each can become accomplished in any branch he wishes, society regulates the general production and thus makes it possible for me to do one thing today and another tomorrow, to hunt in the morning, fish in the afternoon, rear cattle in the evening, criticize after dinner, just as I have a mind, without ever becoming hunter, fisherman, shepherd or critic.”
—Karl Marx (1818–1883)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)