Greatest common divisor of two polynomials

From Wikipedia, the free encyclopedia

The greatest common denominator of two polynomials p(x) and q(x) (with coefficients from a field) is the unique monic polynomial d(x) of highest degree such that :

• d(x) is a common divisor of p(x) and q(x)
• if h(x) is a common divisor of p(x) and q(x) then h(x) divides d(x).

There are several ways to find the greatest common divisor (or highest common factor) of two polynomials. Some of them include:

1. In the usual method, factorization, one finds the factors of each expression, then selects the set of common factors held by all from within each set of factors.
2. Using the Euclidean Algorithm, one can find the GCD of 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). ^[1]

Contents 1 Algebraic proof of the Vedic HCF method 2 Examples 2.1 Example one: Method one, factorization 2.2 Example one: Method two, Euclid’s Algorithm 2.3 Example one: the Vedic Method 2.4 Example two: Vedic method 2.5 Example three: factorization 2.6 Example three: Vedic method 2.7 Example four: Vedic method 3 See also 4 References

[edit] Algebraic proof of the Vedic HCF method

Let P and Q be two expressions. Let H be their HCF. Let A and B be the quotients (after dividing by the HCF). 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±B) Therefore, the HCF of P and Q is also the HCF 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 HFC appears and shows itself! ^[2]

[edit] Examples

[edit] Example one: Method one, factorization

Find the HCF of x2+7x+6 and x2-5x-6. 
x2+7x+6 = (x+1)(x+6)  
x2-5x-6 = (x+1)(x-6)  
Thus, their HFC = (x+1).  

[edit] Example one: Method two, Euclid’s Algorithm

Divide the small expression into the large, then divide the remainder into the small number, and repeat the process. Let x = 10 for the two polynomials. The small number = x²-5x-6 = 100-50-6 = 44. The large number = x²+7x+6 = 100+70+6 = 176.

44 is the divisor when there is no remainder. Next, convert 44 back to polynomial form: 44 = 4x + 4. As there is no factor of four in the expressions we divide by 4 to give (x+1). The HCF = (x+1).

[edit] Example one: the Vedic Method

Find the HCF 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 HCF.

            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 HCF = (x+1).

[edit] 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 HCF = (x2-5x+6)  

[edit] Example three: factorization

Find the HCF 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 HCF.  

[edit] Example three: Vedic method

Find the HCF 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 HCF = (x2 -x -2)  

[edit] Example four: Vedic method

Find the HCF 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)(3x2  -5x    +7)  
                    The HCF = (3x3 –5x2 +7)

[edit] See also

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

[edit] 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.