﻿

# Greatest common divisor of two polynomials

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.

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\left(x + 3\right) = x^2 + 3x$,:$x\left(x + 1\right) = x^2 + x$,and:$\left(x + 3\right)\left(x + 4\right) = x^2 + 7x + 12 = x^2 + x$,after reduction modulo six (see modular arithmetic).This shows that "x" and $x + 3$ would both satisfy the definition of $GCD\left(x^2 + x, x^2 + 3x\right)$.

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.

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\left(p\left(x\right), q\left(x\right)\right)=GCD\left(q\left(x\right),p\left(x\right)\right)$.
*$GCD\left(p\left(x\right), q\left(x\right)\right)=GCD\left(p\left(x\right),p\left(x\right)+q\left(x\right)\right)$.
*For any nonzero scalar "k" in "F", $GCD\left(p\left(x\right),q\left(x\right)\right)=GCD\left(p\left(x\right),kq\left(x\right)\right)$.
*Hence $GCD\left(p\left(x\right),q\left(x\right)\right)=GCD\left(a_1p\left(x\right)+b_1q\left(x\right),a_2p\left(x\right)+b_2q\left(x\right)\right)$ for any scalars $a_1, b_1, a_2, b_2$ such that $a_1 b_2 - a_2 b_1$ is not equal to zero.
*Likewise, if $GCD\left(p\left(x\right), r\left(x\right)\right)=1$, then $GCD\left(p\left(x\right), q\left(x\right)\right)=GCD\left(p\left(x\right), q\left(x\right)r\left(x\right)\right)$.
*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\left(x\right) = p\left(x\right)r\left(x\right) + q\left(x\right)s\left(x\right)$.
*It is possible to define the GCD of three or more polynomials inductively. Explicitly::$GCD\left(p\left(x\right), q\left(x\right), r\left(x\right)\right) = GCD\left(p\left(x\right), GCD\left(q\left(x\right), r\left(x\right)\right)\right)$, and:$GCD\left(p_1\left(x\right), p_2\left(x\right), ..., p_n\left(x\right)\right) = GCD\left( p_1\left(x\right), GCD\left(p_2\left(x\right), ..., p_n\left(x\right)\right)\right)$.

Methods for finding the GCD

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

#"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.
#The "Euclidean Algorithm", which can be used to find the GCD of two polynomials in the same manner as for two numbers.

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"2 + 7"x" + 6 and "x"2 − 5"x" − 6.

"x"2 + 7"x" + 6 = ("x" + 1)("x" + 6)

"x"2 − 5"x" − 6 = ("x" + 1)("x" − 6)

Thus, their GCD = ("x" + 1).

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"2 + 7"x" + 6 and "x"2 − 5"x" − 6.

"x"2 + 7"x" + 6 = ("x"2 − 5"x" − 6)(1) + ("x" + 1)(12)

"x"2 − 5"x" − 6 = ("x" + 1)("x" − 6) + 0"

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

A larger example

Find $GCD\left(8x^5+28x^4+34x^3+41x^2+35x-14,~12x^5+4x^4-27x^3-9x^2-84x-28\right)$.

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^5+28x^4+34x^3+41x^2+35x-14=\left(x+2\right)\left(8x^4+12x^3+10x^2+21x-7\right)$. No more rational roots exist, but with a computer, or a lot of patience, we can get a complete factorization over the rationals:$8x^5+28x^4+34x^3+41x^2+35x-14=\left(x+2\right)\left(4x^2+7\right)\left(2x^2+3x-1\right)$.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^5+4x^4-27x^3-9x^2-84x-28=\left(x+2\right)\left(x-2\right)\left(x+1/3\right)\left(12x^2+21\right)$.Pulling out the leading coefficients, we have:$GCDleft \left[8left\left(x+2 ight\right)left\left(x^2+frac\left\{7\right\}\left\{4\right\} ight\right)left\left(x^2+frac\left\{3\right\}\left\{2\right\}x-frac\left\{1\right\}\left\{2\right\} ight\right),~12left\left(x+2 ight\right)left\left(x-2 ight\right)left\left(x+frac\left\{1\right\}\left\{3\right\} ight\right)left\left(x^2+frac\left\{7\right\}\left\{4\right\} ight\right) ight\right]$:$=left\left(x+2 ight\right)left\left(x^2+frac\left\{7\right\}\left\{4\right\} ight\right)$:$=x^3+2x^2+frac\left\{7\right\}\left\{4\right\}x+frac\left\{7\right\}\left\{2\right\}$.

Euclidean Algorithm

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

:$12x^5+4x^4+27x^3-9x^2-84x-28 =frac\left\{3\right\}\left\{2\right\}\left(8x^5+28x^4+34x^3+41x^2+35x-14\right)+left\left(-38x^4-78x^3-frac\left\{141\right\}\left\{2\right\}x^2-frac\left\{273\right\}\left\{2\right\}x-7 ight\right)$:$8x^5+28x^4+34x^3+41x^2+35x-14=left\left(-frac\left\{4\right\}\left\{19\right\}x-frac\left\{110\right\}\left\{361\right\} ight\right)left\left(-38x^4-78x^3-frac\left\{141\right\}\left\{2\right\}x^2-frac\left\{273\right\}\left\{2\right\}x-7 ight\right)+left\left(-frac\left\{1664\right\}\left\{361\right\}x^3-frac\left\{3328\right\}\left\{361\right\}x^2-frac\left\{2912\right\}\left\{361\right\}x-frac\left\{5824\right\}\left\{361\right\} ight\right)$:$-38x^4-78x^3-frac\left\{141\right\}\left\{2\right\}x^2-frac\left\{273\right\}\left\{2\right\}x-7=left\left(frac\left\{6859\right\}\left\{832\right\}x+frac\left\{361\right\}\left\{832\right\} ight\right)left\left(-frac\left\{1664\right\}\left\{361\right\}x^3-frac\left\{3328\right\}\left\{361\right\}x^2-frac\left\{2912\right\}\left\{361\right\}x-frac\left\{5824\right\}\left\{361\right\} ight\right)+0$The last non-zero remainder was $-frac\left\{1664\right\}\left\{361\right\}x^3-frac\left\{3328\right\}\left\{361\right\}x^2-frac\left\{2912\right\}\left\{361\right\}x-frac\left\{5824\right\}\left\{361\right\}$; to get a monic answer, we multiply through by $-frac\left\{361\right\}\left\{1664\right\}$::$GCD\left(8x^5+28x^4+34x^3+41x^2+35x-14,~12x^5+4x^4-27x^3-9x^2-84x-28\right)=-frac\left\{361\right\}\left\{1664\right\}left\left(-frac\left\{1664\right\}\left\{361\right\}x^3-frac\left\{3328\right\}\left\{361\right\}x^2-frac\left\{2912\right\}\left\{361\right\}x-frac\left\{5824\right\}\left\{361\right\} ight\right)$:$=x^3+2x^2+frac\left\{7\right\}\left\{4\right\}x+frac\left\{7\right\}\left\{2\right\}$.

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.

ee also

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

References

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Greatest common divisor — In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more non zero integers, is the largest positive integer that divides the numbers without a remainder. For …   Wikipedia

• greatest common divisor — noun the largest integer that divides without remainder into a set of integers • Syn: ↑greatest common factor, ↑highest common factor • Hypernyms: ↑common divisor, ↑common factor, ↑common measure * * * noun …   Useful english dictionary

• greatest common divisor — noun Date: 1851 the largest integer or the polynomial of highest degree that is an exact divisor of each of two or more integers or polynomials called also greatest common factor …   New Collegiate Dictionary

• Polynomial — In mathematics, a polynomial (from Greek poly, many and medieval Latin binomium, binomial   , the word has been introduced, in Latin, by Franciscus Vieta) is an expression of finite length constructed from variables (also known as… …   Wikipedia

• Gröbner basis — In computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring R. One can view it as a multivariate, non linear… …   Wikipedia

• Polynomial long division — In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalised version of the familiar arithmetic technique called long division. It can be done easily by hand,… …   Wikipedia

• List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

• Деление многочленов столбиком — В алгебре деление многочленов столбиком  алгоритм деления многочлена на многочлен , степень которого меньше или равна степени многочлена . Алгоритм представляет собой обобщенную форму деления чисел столбиком, легко реализуемую вручную. Для… …   Википедия

• Root-finding algorithm — A root finding algorithm is a numerical method, or algorithm, for finding a value x such that f(x) = 0, for a given function f. Such an x is called a root of the function f. This article is concerned with finding scalar, real or complex roots,… …   Wikipedia

• Ring (mathematics) — This article is about algebraic structures. For geometric rings, see Annulus (mathematics). For the set theory concept, see Ring of sets. Polynomials, represented here by curves, form a ring under addition and multiplication. In mathematics, a… …   Wikipedia