1 Attachment(s)

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) $\displaystyle \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) $\displaystyle \leq $ deg g(x)

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

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

Suppose we have:

f(x) = $\displaystyle q_1 (x)g(x) + r_1(x) $

f(x) = $\displaystyle q_2 (x)g(x) + r_2(x) $

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

Subtracting the two equations give we get

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

Hence

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

We must have $\displaystyle r_2(x) - r_1(x) = 0 $, for otherwise deg $\displaystyle [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 "$\displaystyle r_2(x) - r_1(x) = 0 $, for otherwise deg $\displaystyle [r_2(x) - r_1(x)] \leq $ deg g(x) which would makje equation (3) impossible " follows?

Re: Rings of Polynomials _ Division ALgorithm

Quote:

Originally Posted by

**Bernhard** Suppose we have:

f(x) = $\displaystyle q_1 (x)g(x) + r_1(x) $

f(x) = $\displaystyle q_2 (x)g(x) + r_2(x) $

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

First, it should say $\displaystyle \deg r_i(x) < \deg g(x)$.

Quote:

Originally Posted by

**Bernhard** Subtracting the two equations give we get

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

Hence

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

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

In general, if $\displaystyle s_1(x)\ne0$, then $\displaystyle \deg s_1(x)s_2(x)\ge\deg s_2(x)$. So, if $\displaystyle q_1(x)\ne q_2(x)$, then $\displaystyle \deg [q_1(x) - q_2(x)]g(x)\ge\deg g(x)$. On the other hand, $\displaystyle \deg r_2(x)<\deg g(x)$ and $\displaystyle \deg r_1(x)<\deg g(x)$, so $\displaystyle \deg (r_2(x)-r_1(x))<\deg g(x)$.

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 r_{1}(x) ≠ r_{2}(x), then deg(r_{1} - r_{2}) = max{deg(r_{1}),deg(r_{2})} > -∞

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

since deg(r_{1}) < deg(g), and deg(r_{2}) < deg(g), it follows that -∞ < deg(r_{1} - r_{2}) < deg(g).

now deg((q_{1}-q_{2})(g)) = deg(q_{1} - q_{2}) + 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 q_{1} - q_{2} = 0.

however, if q_{1} - q_{2} = 0, we get:

(q_{1}(x) - q_{2}(x))(g(x)) = (0)(g(x)) = 0 (0 here means the 0-polynomial, and not the field element)

and since (q_{1}(x) - q_{2}(x))(g(x)) = r_{1}(x) - r_{2}(x), if q_{1} = q_{2}, r_{1} = r_{2}.

since this violates our assumption that r_{1} ≠ r_{2}, we can rule out this niggling doubt, and say with confidence:

deg((q_{1}-q_{2})(g)) ≥ deg(g) > deg(r_{1} - r_{2}),

which is a contradiction, since (q_{1}-q_{2})(g) = r_{1} - r_{2}

(equal polynomials have the SAME degree).

since r_{1} ≠ r_{2} leads to a contradiction, it must be the case that this cannot happen, so in point of fact it must be that r_{1} = r_{2}.

since F[x] is an integral domain (this is important!!!), from (q_{1} - q_{2})(g) = 0, and g ≠ 0, w conclude q_{1} - q_{2} = 0, that is:

q_{1} = q_{2}.

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

perhaps you recall when you were looking at "group rings" over a field: F[G]. what polynomials are, are "monoid rings", of the monoid $\displaystyle (\mathbb{N},+)$, over the ring (we in general, for most things only need the ring properties of the field F) F, $\displaystyle 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 "x^{n}" 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:

(x^{m})(x^{n}) = x^{m+n}

Re: Rings of Polynomials _ Division ALgorithm

Thanks for a very helpful post!

Will now work through your post in detail.

Peter

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 (q_{1} - q_{2})(g) = 0, and g ≠ 0, w conclude q_{1} - q_{2} = 0, that is:

q_{1} = q_{2}.'

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

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