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(x\; +\; 3)\; =\; x^2\; +\; 3x$,:$x(x\; +\; 1)\; =\; x^2\; +\; x$,and:$(x\; +\; 3)(x\; +\; 4)\; =\; 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(x^2\; +\; x,\; x^2\; +\; 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.

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\_1p(x)+b\_1q(x),a\_2p(x)+b\_2q(x))$ 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(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\_1(x),\; p\_2(x),\; ...,\; p\_n(x))\; =\; GCD(\; p\_1(x),\; GCD(p\_2(x),\; ...,\; p\_n(x)))$.

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

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

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

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

"x"² − 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(8x^5+28x^4+34x^3+41x^2+35x-14,~12x^5+4x^4-27x^3-9x^2-84x-28)$.

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=(x+2)(8x^4+12x^3+10x^2+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^5+28x^4+34x^3+41x^2+35x-14=(x+2)(4x^2+7)(2x^2+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^5+4x^4-27x^3-9x^2-84x-28=(x+2)(x-2)(x+1/3)(12x^2+21)$.Pulling out the leading coefficients, we have:$GCDleft\; [8left(x+2\; ight)left(x^2+frac\{7\}\{4\}\; ight)left(x^2+frac\{3\}\{2\}x-frac\{1\}\{2\}\; ight),~12left(x+2\; ight)left(x-2\; ight)left(x+frac\{1\}\{3\}\; ight)left(x^2+frac\{7\}\{4\}\; ight)\; ight]$:$=left(x+2\; ight)left(x^2+frac\{7\}\{4\}\; ight)$:$=x^3+2x^2+frac\{7\}\{4\}x+frac\{7\}\{2\}$.

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

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