# Questions about proof of the division article.

Dafe
Hi,

I am reading this proof of the division article:
http://xmlearning.maths.ed.ac.uk/lecture_notes/polynomials/division_algorithm/division_algorithm.php" [Broken]

I will write some of it here in case you don't want to click on any links.
Theorem: Let $$f,g \in R[X]$$ be polynomials with $$g \neq$$.
Then there exist unique polynomials $$q,r \in R[X]$$ such that $$f=gq+r$$ and $$deg(r)<deg(g)$$.

Proof: We first prove existence of $$q,r$$.
If $$deg(g)>deg(f)$$ then we set $$q=0$$ and $$r=f$$.
Otherwise, $$deg(f) \geq deg(g)$$

Let,
$$f=a_0+...+a_mX^m$$ where $$a_m \neq 0$$.
and
$$g=b_0+...+b_nX^n$$ where $$b_n \neq 0$$.

Define the integer $$d=m-n \geq 0$$. We will use induction in $$d$$.

Base step: Let $$d=0$$, then $$m=n$$. We set $$q=\frac{a_m}{b_m}$$.

I will stop there.
How come they set $$q=\frac{a_m}{b_m}$$?
Since $$f(x)=q(x)g(x)+r(x)$$ isn't then
$$q(x)=\frac{f(x)}{g(x)} - \frac{r(x)}{g(x)}$$ ?

Last edited by a moderator:

Homework Helper
Hi,

I am reading this proof of the division article:
http://xmlearning.maths.ed.ac.uk/lecture_notes/polynomials/division_algorithm/division_algorithm.php" [Broken]

I will write some of it here in case you don't want to click on any links.
Theorem: Let $$f,g \in R[X]$$ be polynomials with $$g \neq$$.
Then there exist unique polynomials $$q,r \in R[X]$$ such that $$f=gq+r$$ and $$deg(r)<deg(g)$$.

Proof: We first prove existence of $$q,r$$.
If $$deg(g)>deg(f)$$ then we set $$q=0$$ and $$r=f$$.
Otherwise, $$deg(f) \geq deg(g)$$

Let,
$$f=a_0+...+a_mX^m$$ where $$a_m \neq 0$$.
and
$$g=b_0+...+b_nX^n$$ where $$b_n \neq 0$$.

Define the integer $$d=m-n \geq 0$$. We will use induction in $$d$$.

Base step: Let $$d=0$$, then $$m=n$$. We set $$q=\frac{a_m}{b_m}$$.

I will stop there.
How come they set $$q=\frac{a_m}{b_m}$$?
Since $$f(x)=q(x)g(x)+r(x)$$ isn't then
$$q(x)=\frac{f(x)}{g(x)} - \frac{r(x)}{g(x)}$$ ?

In this "base case", d= 0, the two polynomials have the same degree and so their quotient is a number, not a function of x. For example, if $f(x)= ax^2+ bx+ c$ and $g(x)= ex^2+ fx+ g$ then
$$\frac{ax^2+ bx+ c}{ex^2+ fx+ g}$$
is just the number a/e with a first degree remainder.

Last edited by a moderator:
Dafe
Thank you One more question (kind of the same):
The article goes on with the induction step:

Now we assume that this is true whenever $$d<k$$ and let $$d=k$$, so that
$$m=n+k$$. Let $$f_1=f-(\frac{a_m}{b_n}x^{m-n}g)$$.

I do not understand this last step.
Since $$\frac{a_m}{b_n}x^{m-n}$$ would be the first step of long division, does $$f_1$$ somehow refer to this?

Feeling quite stupid here. Good thing it's Christmas soon, will drown my sorrows in food and drink.

Thanks again!