Notices
Results 1 to 7 of 7

Thread: Factor theorem

  1. #1 Factor theorem 
    Forum Masters Degree thyristor's Avatar
    Join Date
    Feb 2008
    Location
    Sweden
    Posts
    542
    How do you prove the factor theorem?


    373 13231-mbm-13231 373
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    I'm assuming you mean the following:

    "Let f(x) be a polynomial with coefficients in the real numbers (or complex numbers or any field for that matter), then x-a divides f(x) iff a is a root of f(x)."

    This is a specific instance of a more general fact:

    "The remainder when f(x) is divided by x-a is f(a)."

    This requires knowledge of the division algorithm for polynomials:

    "Let f(x), g(x) be polynomials with coefficients in the real numbers. There exist unique polynomials q(x), r(x) with deg r(x) < deg g(x), f(x) = g(x)q(x)+r(x)."

    To prove the general fact from this, we let g(x) = x-a. Then applying the division algorithm, there are polynomials q(x), r(x) with deg r(x) < deg (x-a) and f(x) = (x-a)q(x)+r(x). Since deg (x-a) = 1, we must have r(x) = b is a constant polynomial. Thus f(x) = (x-a)q(x)+b. Plugging in a, we get f(a) = (a-a)q(a)+b = b, so r(x) = f(a). We then see f(a) = 0 iff the remainder is 0 iff x-a divides f(x).

    The polynomial division algorithm isn't too hard to prove--you can do it pretty easily by induction, say. I can run through this if you'd like.


    Reply With Quote  
     

  4. #3  
    Forum Masters Degree thyristor's Avatar
    Join Date
    Feb 2008
    Location
    Sweden
    Posts
    542
    Yes, please.
    373 13231-mbm-13231 373
    Reply With Quote  
     

  5. #4  
    Forum Masters Degree thyristor's Avatar
    Join Date
    Feb 2008
    Location
    Sweden
    Posts
    542
    Yes, please.
    373 13231-mbm-13231 373
    Reply With Quote  
     

  6. #5  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    So let f(x) have degree n and g(x) have degree m. We assume that g(x) is not the zero polynomial. If n < m (or if, say, f(x) is the 0 polynomial), then we let q(x) = 0 and r(x) = f(x). Otherwise, m ≥ n. Suppose that



    and



    Now note that, whatever q(x) is, we must have deg(q(x)) = n-m. This is because whatever r(x) is, it's supposed to have degree less than m, so it must have degree less than n. The sum of two polynomials has degree at most the maximum of the degree of the summands, and so g(x)q(x) must have degree n, whence q(x) must have degree n-m. So we'll solve for the coefficients of q(x). q(x) has the form



    Multiplying b(x) and q(x), we obtain



    where



    Here, I use the convention that b<sub>i</sub> = 0 unless 0 ≤ i ≤ m and c<sub>j</sub> = 0 unless 0 ≤ j ≤ m-n. Since we want r(x) = f(x) - q(x)b(x) to have degree less than m, we want f(x) and q(x)b(x) to agree for all powers x<sup>k</sup> with m ≤ k ≤ n, i.e. we want a<sub>k</sub> = d<sub>k</sub> for m ≤ k ≤ n. Thus we have m-n+1 unknowns and m-n+1 equations



    (Note that we may have n-m < m, and so any c<sub>k</sub> with k > n-m is 0.) If you know a thing or two about linear algebra, you'll see that you can set this up as a linear equation Bc = a, where B is a square, lower-triangular matrix with entries b<sub>m</sub> going down the diagonal. Since deg(g(x)) = m, we have b<sub>m</sub> ≠ 0, and so this system has a unique solution.

    Even if you don't know linear algebra, you should know simultaneous equations, and this is enough to see what to do: use the first equation to solve for c<sub>n-m</sub>, and then use this new information in the next equation to solve for c<sub>n-m-1</sub>, as the only other unknown in this equation is c<sub>n-m</sub>, and we figured this out already. Now use this new information in the third equation, substituting in the values for the two coefficients we already know to solve for c<sub>n-m-2</sub>. Continue in this fashion--each successive equation involves one new unknown, the rest already having been solved for, and you can always solve for the new unknown, as it's always multiplied by something nonzero--namely, b<sub>m</sub>.

    Since we can solve this equation uniquely, a unique q(x) exists such that f(x) - b(x)q(x) has degree less than m. Now let r(x) = f(x) - b(x)q(x).

    Uniqueness is guaranteed by linear algebraic consideration, but we can show it easily in any case: suppose q(x), r(x), q'(x), r'(x) are two solutions to the division algorithm. Then

    q(x)b(x)+r(x) = q'(x)b(x)+r'(x)

    Thus

    (q(x)-q'(x))b(x) = r'(x)-r(x)

    r'(x)-r(x) has degree less than the degree of b(x), but this equation implies that b(x) divides them. Thus r'(x)-r(x) must be 0, i.e. r'(x) = r(x), and this immediately implies q(x) = q'(x).
    Reply With Quote  
     

  7. #6  
    Forum Masters Degree thyristor's Avatar
    Join Date
    Feb 2008
    Location
    Sweden
    Posts
    542
    Thansk, sorry I made a double-post.
    373 13231-mbm-13231 373
    Reply With Quote  
     

  8. #7  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    No biggie.

    ----------------

    PS: This is my 1000<sup><u>th</u></sup> post!
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •