Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By Deveno

Math Help - Rings of Polynomials _ Division ALgorithm

  1. #1
    Super Member Bernhard's Avatar
    Joined
    Jan 2010
    From
    Hobart, Tasmania, Australia
    Posts
    558
    Thanks
    2

    Rings of Polynomials _ Division ALgorithm

    I am reading Papantonopoulou - Algebra, Ch 8, Rings of Polynomials

    Theorem 8.2.2 (Division Algorithm) reads as follows: (see attachment for full proof)

    Let F be a field and f(x) and g(x) elements of F[x], with g(x)  \neq 0 . Then there exist unique elements Q(x) and r(x) of F[x] such that

    (1) f(x) = q(x)g(x) + r(x)
    (2) r(x) = 0 or deg r(x)  \leq deg g(x)

    ================================================== ================================

    I am having trouble following the uniqueness argument which runs as follows:

    Suppose we have:

    f(x) =  q_1 (x)g(x) + r_1(x)

    f(x) =  q_2 (x)g(x) + r_2(x)

    where r_i(x) = 0 or deg r_i(x) \leq deg g(x).


    Subtracting the two equations give we get

    0 =  [q_1(x) - q_2(x)] g(x) + [r_1(x) - r_2(x)]

    Hence

    (3)  [q_1(x) - q_2(x)]g(x) = r_2(x) - r_1(x)

    We must have  r_2(x) - r_1(x) = 0 , for otherwise deg [r_2(x) - r_1(x)] \leq deg g(x) which would makje equation (3) impossible .... etc etc

    (see the proof on the attachment)
    ================================================== =========================================

    Can anyone show me (formally) why the last statement ie "  r_2(x) - r_1(x) = 0 , for otherwise deg [r_2(x) - r_1(x)] \leq deg g(x) which would makje equation (3) impossible " follows?
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Rings of Polynomials _ Division ALgorithm

    Quote Originally Posted by Bernhard View Post
    Suppose we have:

    f(x) =  q_1 (x)g(x) + r_1(x)

    f(x) =  q_2 (x)g(x) + r_2(x)

    where r_i(x) = 0 or deg r_i(x) \leq deg g(x).
    First, it should say \deg r_i(x) <  \deg g(x).

    Quote Originally Posted by Bernhard View Post
    Subtracting the two equations give we get

    0 =  [q_1(x) - q_2(x)] g(x) + [r_1(x) - r_2(x)]

    Hence

    (3)  [q_1(x) - q_2(x)]g(x) = r_2(x) - r_1(x)

    We must have  r_2(x) - r_1(x) = 0 , for otherwise deg [r_2(x) - r_1(x)] \leq deg g(x) which would makje equation (3) impossible
    In general, if s_1(x)\ne0, then \deg s_1(x)s_2(x)\ge\deg s_2(x). So, if q_1(x)\ne q_2(x), then \deg [q_1(x) - q_2(x)]g(x)\ge\deg g(x). On the other hand, \deg r_2(x)<\deg g(x) and \deg r_1(x)<\deg g(x), so \deg (r_2(x)-r_1(x))<\deg g(x).
    Thanks from Bernhard
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,312
    Thanks
    692

    Re: Rings of Polynomials _ Division ALgorithm

    in general, deg(f+g) = max{deg(f),deg(g)} (the 0-polynomial sort of goobers things up. for this reason deg(0) is often taken to be -∞).

    also deg(fg) = deg(f) + deg(g) (the 0-polynomial REALLY messes with this formula. but see above).

    from the second rule we get deg(-f) = deg((-1)(f)) = deg(-1) + deg(f) = 0 + deg(f) = deg(f).

    now in the proof at hand: if r1(x) ≠ r2(x), then deg(r1 - r2) = max{deg(r1),deg(r2)} > -∞

    (the two remainders can't BOTH be zero, or else they would be equal).

    since deg(r1) < deg(g), and deg(r2) < deg(g), it follows that -∞ < deg(r1 - r2) < deg(g).

    now deg((q1-q2)(g)) = deg(q1 - q2) + deg(g).

    we'd like to show that this is greater than or equal to deg(g), but there is one wrinkle: we might have q1 - q2 = 0.

    however, if q1 - q2 = 0, we get:

    (q1(x) - q2(x))(g(x)) = (0)(g(x)) = 0 (0 here means the 0-polynomial, and not the field element)

    and since (q1(x) - q2(x))(g(x)) = r1(x) - r2(x), if q1 = q2, r1 = r2.

    since this violates our assumption that r1 ≠ r2, we can rule out this niggling doubt, and say with confidence:

    deg((q1-q2)(g)) ≥ deg(g) > deg(r1 - r2),

    which is a contradiction, since (q1-q2)(g) = r1 - r2

    (equal polynomials have the SAME degree).

    since r1 ≠ r2 leads to a contradiction, it must be the case that this cannot happen, so in point of fact it must be that r1 = r2.

    since F[x] is an integral domain (this is important!!!), from (q1 - q2)(g) = 0, and g ≠ 0, w conclude q1 - q2 = 0, that is:

    q1 = q2.

    ************

    perhaps you recall when you were looking at "group rings" over a field: F[G]. what polynomials are, are "monoid rings", of the monoid (\mathbb{N},+), over the ring (we in general, for most things only need the ring properties of the field F) F, F[\mathbb{N}].

    in other words, polynomials in F[x] are F-linear combinations of natural numbers (we identity the natural number n with the "xn" term, or if you like, the n-th coordinate (term) in a finite sequence of field elements).

    more acccurately, we are identifying the monoid (N,+) with the sub-monoid (<x>,*) of (F[x],*). this is why:

    (xm)(xn) = xm+n
    Last edited by Deveno; October 5th 2012 at 03:14 PM.
    Thanks from Bernhard
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bernhard's Avatar
    Joined
    Jan 2010
    From
    Hobart, Tasmania, Australia
    Posts
    558
    Thanks
    2

    Re: Rings of Polynomials _ Division ALgorithm

    Thanks for a very helpful post!

    Will now work through your post in detail.

    Peter
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bernhard's Avatar
    Joined
    Jan 2010
    From
    Hobart, Tasmania, Australia
    Posts
    558
    Thanks
    2

    Re: Rings of Polynomials _ Division ALgorithm

    Yes, followed all that and now understand the proof thanks to the clarity of your post.

    Thank you by the way for the point:

    "since F[x] is an integral domain (this is important!!!), from (q1 - q2)(g) = 0, and g ≠ 0, w conclude q1 - q2 = 0, that is:

    q1 = q2.'

    I had completely missed this point - and yes, it is very important!

    Now will look at polynomials and monoid rings - thanks for that interesting lead ...

    Peter
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2012
    From
    American
    Posts
    3

    Re: Rings of Polynomials _ Division ALgorithm

    I don't know much about this.But I have learned something useful.







    _____________________________________________
    Hermes Birkin|Hermes 30cm Birkin Bags
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Division algorithm for polynomials
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: April 15th 2011, 04:26 PM
  2. division of polynomials in rings
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: November 3rd 2010, 06:33 PM
  3. [SOLVED] Vector spaces over division rings.
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: May 31st 2010, 04:22 PM
  4. Division algorithm/mod
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 13th 2010, 12:51 PM
  5. Division in Polynomial Rings
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: November 4th 2009, 09:20 AM

Search Tags


/mathhelpforum @mathhelpforum