Polynomial – Euclid’s Algorithm for Finding HCF

 

Motivation: 

 

                      For natural numbers, we have Euclid’s algorithm to find the gcd. Similarly, Euclid’s algorithm can be applied on polynomials to find HCF ( highest common factor ) without doing factoring polynomials.

 

 

Theorem ( Euclid’s algorithm )

              f(x), g(x)  F[x].  Let deg(f(x)) and deg(g(x))  stand for the degrees of the corresponding polynomials.  Without loss of generality,  assume deg(f(x))  deg(g(x)).

 

              If there exist  q(x), r(x)  F[x] such that

                         f(x) = g(x) q(x) + r(x)    ,  where  deg(r(x) < deg(g(x))

              then

                          HCF( f(x), g(x) ) = HCF ( g(x), r(x))

 

              By repeatedly using this result,  we can find HCF of f(x) and g(x).

 

    Proof:

                        Let  h(x) = HCF( f(x), g(x)) and  d(x) = HCF( g(x), r(x)) .

 

                        Since h(x) | f(x)  and h(x) | g(x) ,

                            h(x) | ( f(x) – g(x)q(x))

                            h(x) | r(x)

 

                         Thus,   deg( h(x) )  deg( d(x))  (   d(x) = HCF( g(x), r(x) ) )

 

                    On the other hand,    d(x) | g(x) and d(x) | r(x)

                                  d(x) | ( g(x)q(x) + r(x) )

                                  d(x) | f(x)

 

                          Thus,  deg( d(x) )  deg( h(x) )   ( because h(x)=HCF(f(x), g(x)) )

 

                     Hence, we have deg(h(x)) = deg(d(x)) .

                        Both of them are the factors of f(x), g(x), and r(x) .

                        That means they only differ by multiplying a constant term.

 

                     So,  HCF(f(x), g(x)) = HCF( g(x), r(x)) .

 

 

 

 

 

 

Example:  Find HCF of  (x³ + 5x² – 18x – 18 ) and ( x⁴ + 7x³ + 10x + 12 )

 

                  (x⁴ + 7x³ + 10x + 12) =  (x+2)(x³ + 5x² – 18x -18 ) + (8x² +64x + 48)

                                        ( This can be obtained via “long division” method ).

 

                 The problem turns out to be  HCF of (x³ + 5x² – 18x -18 )  and (8x² +64x + 48).

 

             (x³ + 5x² – 18x -18 ) = (x-3)(x² +8x + 6) + 0

 

               So,  the answer is  (x² +8x + 6).

 

               Similarly, the whole process can be perform in the following way:

 

                      1+2   | 1 + 7 + 0 + 10 + 12 |  1 + 5 – 18 – 18  | 1 + 3

                               | 1 + 5 – 18- 18         |   1 + 8 + 6           |

                               | --------------------     |  ------------------  |

                               |        2 +18 + 28+12 |       -3 – 24 – 18  |

                               |        2 +10 – 36-36  |       -3 – 24 – 18  |

                               | ----------------------- |  ------------------- |

                               |               8 + 64 +48|         0 + 0  + 0    |

                               |  div 8:   ------------- |

                               |                1 + 8 + 6  |