Polynomial greatest common divisor

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). When dealing with numbers, the definition is similar. If you have two whole numbers, the greatest common divisor of those numbers is simply the biggest whole number that you can divide into both of them while getting a remainder of zero. The greatest common divisor is also sometimes referred to as the greatest common factor or the highest common factor.

Formal Definition

The greatest common divisor of two polynomials p(x) and q(x), not both zero, with coefficients from a field is the monic polynomial d(x) of highest degree such that d(x) is a common divisor of both p(x) and q(x).

The definition is very specific and this is very important. For example, if both polynomials were zero, then any polynomial would divide them both. In this case, there would be no greatest common divisor. Thus, at least one of the polynomials must be nonzero.

Also, if there were no requirement for the GCD to be monic, there could be several different, even an infinite number of different, GCDs for any two polynomials. This results because any nonzero constant multiple (with constants from the field) of the monic common divisor of highest degree is still a common divisor of highest degree.

Finally, the definition states the coefficients must come from a field. If the coefficients could come from any ring, then factorization would not necessarily be unique. For example, in Z6,

$(2x+1)(3x+1)=6x^{2}+5x+1=5x+1$

and

$5(x+5)=5x+25=5x+1$.

All of these details together ensure that there is a GCD and that the GCD is unique.

Properties

• As stated above, the GCD of two nonzero polynomials, with coefficients from a field, 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.
• The GCD of two polynomials, p(x) and q(x), 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)$.

Methods for finding the GCD

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

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.
3. Swami Bharati Krishna Tirtha's Vedic mathematics contains a method, here called the Vedic method, which is mainly an application of the Lopana-Sthapana Sutra, the Sankalna-Vyavakalan process, and the Adyamadya rule. The sutra is a formula for the alternate destruction of the highest and lowest powers (by the addition or subtraction of multiples of the coefficients).

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).

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 division with remainder, 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^2 - 5x - 6 = (x + 1)(x - 6) + 0

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

Algebraic proof of the Vedic method for finding the GCD

Let P and Q be two expressions. Let H be their GCD. Let A and B be the quotients (after dividing by the GCD). Therefore, P/H = A and Q/H = B and also P = HA and Q = HB. Therefore P±Q = H(A±B) and MP±NQ = H(MA±NB) Therefore, the GCD of P and Q is also the GCD of P±Q, 2P±Q, P±2Q, and MP±NQ. So, when we select our M and N so that the highest and lowest powers are removed, then the GCD appears and shows itself!

Examples

Example one: the Vedic Method

Find the GCD of x²+7x+6 and x²-5x-6. To eliminate the x-squared terms, just subtract the expressions. To eliminate the constant terms, simply add the two expressions. Then, pull out any common factors to reveal the GCD.

            x2+7x+6                      x2+7x+6  
Subtract: -(x2-5x-6)             Add: + (x2-5x-6)  
              12x+12 = 12(x+1)          2x2+2x   = 2x(x+1)  
Thus, their GCD = (x+1).

Example two: Vedic method

   E1 = x3 –3x2 - 4x +12     E2 = x3 – 7x2 +16x -12  
Minus -(x3 –7x2 +16x –12)   Add +(x3 – 3x2 - 4x +12)  
            4x2 –20x +24         2x3 -10x2 +12x 
Remove common factors: 4(x2–5x +6)    2x(x2-5x+6) 
 Their GCD = (x2-5x+6)

Example three: factorization

Find the GCD of the two expressions after factorization:

     E1 = x4 + x3 –5x2 -3x +2  = (x+1)(x-2)(x2+2x-1)  
 and E2 = x4 -3x3 + x2 +3x -2  = (x+1)(x-2)(x-1)2  
Seeing the shared factors are the binomials (x+1)(x-2) we have 
them as the GCD.  

Example three: Vedic method

Find the GCD of two expressions by elimination and retention of the highest and the lowest powers.

    E1 = x4 + x3 –5x2 -3x +2            E1 = x4 + x3 –5x2 -3x +2
and E2 = x4 -3x3 + x2 +3x -2            E2 = x4 -3x3 + x2 +3x -2
The sum: 2x4 –2x3 –4x2         Their difference: 4x3 –6x2 –6x +4
Pull out the common factors: 
   (2x2)(x2 –x -2)                           (2)(2x3 –3x2 –3x +2)
Restore a factor of (2x) for a second elimination.  
Multiply by (2x)(x2 –x -2) = 2x3 –2x2 –4x 
Subtract second result from first result:     2x3 –3x2 –3x + 2  
                                      Minus -(2x3 –2x2 –4x )                                                                                   
                                                  – x2  +x + 2  
Since the expressions have positive x2 terms remove the factor of -1:
                                        Their GCD = (x2 -x -2)

Example four: Vedic method

Find the GCD of two expressions.  
E1 = 6x4 – 7x3 – 5x2 + 14x +7                E2 = 3x3 – 5x2 +7  
To eliminate the 4th power: E1 + (-2x)(E2). 
Subtract: E1 - E2 to eliminate the constant terms.  
                       6x4 – 7x3 –5x2 +14x +7     6x4 – 7x3 –5x2 +14x +7  
(-2x)(3x3–5x2+7)= add +(6x4 +10x3     –14x)     Minus -(3x3 –5x2      +7)  
                             3x3 –5x2      +7     6x4 –10x3     +14x 
                    Take out the common factor: (2x)(3x3  -5x2    +7)  
                    The GCD = (3x3 –5x2 +7)

See also

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

References

• Vedic Mathematics: Sixteen Simple Mathematical Formulae from the Vedas, by Swami Sankaracarya (1884-1960), Motilal Banarsidass Indological Publishers and Booksellers, Varnasi, India, 1965; reprinted in Delhi, India, 1975, 1978. 367 pages.