Rings of Polynomials _ Division ALgorithm

• Oct 5th 2012, 02:36 AM
Bernhard
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?
• Oct 5th 2012, 03:00 AM
emakarov
Re: Rings of Polynomials _ Division ALgorithm
Quote:

Originally Posted by Bernhard
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
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)$.
• Oct 5th 2012, 03:05 PM
Deveno
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
• Oct 5th 2012, 04:25 PM
Bernhard
Re: Rings of Polynomials _ Division ALgorithm
Thanks for a very helpful post!

Will now work through your post in detail.

Peter
• Oct 5th 2012, 05:30 PM
Bernhard
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
• Oct 22nd 2012, 02:05 AM