Greatest common divisor of two polynomials

From Wikipedia, the free encyclopedia

This article is in need of attention from an expert on the subject. WikiProject Mathematics or the Mathematics Portal may be able to help recruit one. If a more appropriate WikiProject or portal exists, please adjust this template accordingly.

Informally, the greatest common divisor (GCD) of two polynomials p(x) and q(x) is the "biggest" polynomial that divides evenly into both p(x) and q(x). The definition is modeled on the concept of the greatest common divisor of two integers. This is simply the greatest integer that divides into both of them with a remainder of zero. For polynomials, the situation is slightly more complicated, because there is no canonical order which we can use to say which polynomial is "biggest." Instead, we choose the GCD so that its degree is as great as possible, and so that its leading coefficient equals one (i.e a monic polynomial). The greatest common divisor is also sometimes referred to as the greatest common factor or the highest common factor.

Contents 1 Formal Definition 2 Properties 3 Methods for finding the GCD 3.1 Factoring 3.2 Euclidean Algorithm 4 A larger example 4.1 Factorization method 4.2 Euclidean Algorithm 4.3 Comparing the methods 5 See also 6 References

[edit] Formal Definition

Let p(x) and q(x) be polynomials, not both zero, with coefficients in a field F. The greatest common divisor of p(x) and q(x) is the monic polynomial d(x) of highest degree such that d(x) is a divisor of p(x) and of q(x). We may denote the greatest common divisor of p(x) and q(x) by GCD(p(x), q(x)).

F may be, for example, the complex numbers, the real numbers or the rational numbers.

If p(x)=q(x)=0, then every polynomial is a common divisor of p(x) and q(x). Thus no greatest common divisor exists in this case.

We require that F be a field and that d(x) be monic. Under these two hypotheses, the GCD exists and is uniquely defined. They are necessary hypotheses. For example, suppose we allow F=Z/6Z, which is not a field. Then we have

x(x + 3) = x² + 3x,

x(x + 1) = x² + x,

and

(x + 3)(x + 4) = x² + 7x + 12 = x² + x,

after reduction modulo six (see modular arithmetic). This shows that x and x + 3 would both satisfy the definition of GCD(x² + x,x² + 3x).

Suppose, on the other hand, that we did not require d(x) to be monic. In that case, whenever d(x) satisfied the definition of GCD(p(x), q(x)), so would k•d(x) for any nonzero scalar k in F. Again, the GCD would not be uniquely determined.

The constant 1 is always a common divisor of p(x) and q(x); we may regard it as a monic polynomial of degree zero. If GCD(p(x), q(x))=1, we say p and q are relatively prime.

[edit] Properties

• As stated above, the GCD of two polynomials, not both zero, with coefficients from a field, exists and is unique.
• If c(x) is any common divisor of p(x) and q(x), then c(x) divides d(x). This is sometimes given in the definition instead of requiring d(x) to be the common divisor of highest degree. The two definitions are logically equivalent.
• GCD(p(x),q(x)) = GCD(q(x),p(x)).
• GCD(p(x),q(x)) = GCD(p(x),p(x) + q(x)).
• For any nonzero scalar k in F, GCD(p(x),q(x)) = GCD(p(x),kq(x)).
• Hence GCD(p(x),q(x)) = GCD(a₁p(x) + b₁q(x),a₂p(x) + b₂q(x)) for any scalars a₁,b₁,a₂,b₂ such that a₁b₂ − a₂b₁ is not equal to zero.
• Likewise, if GCD(p(x),r(x)) = 1, then GCD(p(x),q(x)) = GCD(p(x),q(x)r(x)).
• The GCD of two polynomials, p(x) and q(x), is the smallest-degree polynomial which can be written as a linear combination of p(x) and q(x). That is, there exist some polynomials, in the same field, r(x) and s(x), not necessarily unique, such that

d(x) = p(x)r(x) + q(x)s(x).

• It is possible to define the GCD of three or more polynomials inductively. Explicitly:

GCD(p(x),q(x),r(x)) = GCD(p(x),GCD(q(x),r(x))), and

GCD(p₁(x),p₂(x),...,p_n(x)) = GCD(p₁(x),GCD(p₂(x),...,p_n(x))).

[edit] Methods for finding the GCD

There are several ways to find the greatest common divisor of two polynomials. Two of them are:

1. Factorization, in which one finds the factors of each expression, then selects the set of common factors held by all from within each set of factors.
2. The Euclidean Algorithm, which can be used to find the GCD of two polynomials in the same manner as for two numbers.

[edit] Factoring

To find the GCD of two polynomials using factoring, simply factor the two polynomials completely. Then, take the product of all common factors. At this stage, we do not necessarily have a monic polynomial, so finally multiply this by a constant to make it a monic polynomial. This will be the GCD of the two polynomials as it includes all common divisors and is monic.

Example One

Find the GCD of x² + 7x + 6 and x² − 5x − 6.

x² + 7x + 6 = (x + 1)(x + 6)

x² − 5x − 6 = (x + 1)(x − 6)

Thus, their GCD = (x + 1).

[edit] Euclidean Algorithm

Finding the GCD by factoring is intuitively simple but requires knowing how to factor the polynomials, which can be difficult, especially if the polynomials have large degree. The Euclidean Algorithm is a fast method which works for any pair of polynomials. It makes repeated use of polynomial long division, just as when the Euclidean Algorithm is applied to two numbers. When using the Euclidean Algorithm on two numbers, the size of the numbers decreases at each stage. With polynomials, the degree of the polynomials decreases at each stage. The last nonzero remainder, made monic if necessary, is the GCD of the two polynomials.

Example One

Find the GCD of x² + 7x + 6 and x² − 5x − 6.

x² + 7x + 6 = (x² − 5x − 6)(1) + (x + 1)(12)

x² − 5x − 6 = (x + 1)(x − 6) + 0

Since x + 1 is the last nonzero remainder, the GCD of these polynomials is x + 1.

[edit] A larger example

Find .

[edit] Factorization method

The rational root theorem gives some possible linear factors which can be tested by synthetic division; some trial and error gives:

    |     8    28    34    41    35   -14
    |
 -2 |         -16   -24   -20   -42    14
----|---------------------------------------------
    |     8    12    10    21    -7    (0)
    |

So 8x⁵ + 28x⁴ + 34x³ + 41x² + 35x − 14 = (x + 2)(8x⁴ + 12x³ + 10x² + 21x − 7). No more rational roots exist, but with a computer, or a lot of patience, we can get a complete factorization over the rationals: 8x⁵ + 28x⁴ + 34x³ + 41x² + 35x − 14 = (x + 2)(4x² + 7)(2x² + 3x − 1). Turning to the other polynomial, we have:

     |    12     4   -27    -9   -84   -28
     |
 -2  |         -24    40   -26    70    28
-----|---------------------------------------------
     |    12   -20    13   -35   -14    (0)
     |
  2  |          24     8    42    14
-----|---------------------------------------------
     |    12     4    21     7    (0)
     |
-1/3 |          -4     0    -7
-----|---------------------------------------------
     |    12     0    21    (0)
     |

This shows: 12x⁵ + 4x⁴ − 27x³ − 9x² − 84x − 28 = (x + 2)(x − 2)(x + 1 / 3)(12x² + 21). Pulling out the leading coefficients, we have:

.

[edit] Euclidean Algorithm

To get started, we pick either polynomial and divide it by the other.

The last non-zero remainder was ; to get a monic answer, we multiply through by :

.

[edit] Comparing the methods

The solution by the Euclidean algorithm looks more complicated than the factorization, especially because of the fractions with large denominators. However, factorization is actually harder in this case, because a lot of invisible work is required to get the complete factorization.

[edit] See also

• Euclidean algorithm
• Greatest common divisor
• List of polynomial topics
• Multivariate division algorithm
• Synthetic division

[edit] References