# 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 thegreatest 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 nocanonical 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 itsleading 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 themonic polynomial "d"("x") of highest degree such that "d"("x") is adivisor 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 , thereal numbers or therational 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**/6**Z**, 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 (seemodular 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"

^{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 ofpolynomial 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(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**

*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 [1] [2] [3], the word has been introduced, in Latin, by Franciscus Vieta[4]) 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