- #1

CGandC

- 279

- 23

**Let ## f(x), g(x) \in \mathbb{F}[ x] ## by polynomials, s.t. the degree of ## g(x) ## is at least ## 1 ##. Then: there are polynomials ## q(x), r(x) \in \mathbb{F}[ x] ## s.t.**

__Theorem:__1. ## f(x)=q(x) \cdot g(x)+r(x) ##

or

2. the degree of ## r(x) ## is less than the degree of ## g(x) ##

**Proof ( from lecture notes ):**

Let ## k ## be the degree of polynomial ## f(x) ## and ## m ## the degree of polynomial ## g(x) ##. It is given that ## 1 \leq m ##. The proof is by induction on ## k ##.

__Induction basis:__## k < m ##. Since ## f(x)=0 \cdot g(x)+f(x) ## ,

we can take ## r(x) = f(x) ##, ## q(x) = 0 ## and the two requirements requirements of the theorem are satisfied.

__Induction step__( ## m \leq k ## ): Suppose the theorem's true for polynomials of degree less than ## k ##, we'll prove for polynomials of degree ## k ##.

We'll write the polynomials ## f(x),g(x) ## explicitly:

## f(x)=a_{0}+a_{1} x+\cdots+a_{k-1} x^{k-1}+a_{k} x^{k} ##

## g(x)=b_{0}+b_{1} x+\cdots+b_{m-1} x^{m-1}+b_{m} x^{m}##

where ## a_k, b_m ## are different from zero. We'll define a polynomial of the same degree and with the same leading coefficient like ## f(x) ##:

##. h(x)=\frac{a_{k}}{b_{m}} x^{k-m} g(x)=\frac{a_{k}}{b_{m}} x^{k-m}\left(\left(b_{0}+b_{1} x+\cdots+b_{m-1} x^{m-1}\right)+b_{m} x^{m}\right) ##

##=\frac{a_{k}}{b_{m}} x^{k-m}\left(b_{0}+b_{1} x+\cdots+b_{m-1} x^{m-1}\right)+a_{k} x^{k} ##

Then the degree of ## f(x) - h(x) ## is less than ## k ##. From the induction hypothesis, there are polynomials ## q_0(x) , r(x) ## s.t. ## f(x)-h(x)=q_{0}(x) \cdot g(x)+r(x) ## and the degree of polynomial ## r(x) ## is less than the degree of ## g(x) ##. We'll move ## h(x) ## a side and we'll get

## f(x)=q_{0}(x) \cdot g(x)+h(x)+r(x)=q_{0}(x) \cdot g(x)+\frac{a_{k}}{b_{m}} x^{k-m} g(x)+r(x) ##

##=\underbrace{\left(q_{0}(x)+\frac{a_{k}}{b_{m}} x^{k-m}\right)}_{q(x) \in \mathbb{F}[ x]} \cdot g(x)+r(x) ##

, as wanted , QED.

I don't see how the proof by induction is being done here.

__My question:__I don't see how the proof by induction is being done here.

I learned that If I have a claim of the form ## \forall n \in \mathbb N . P(n) ## , where ## P(n) ## is a claim that depends on ## n ##, then I can prove by induction by showing that ## P(0) ## holds and showing that ## \forall n > 0 . P(n) \rightarrow P(n+1) ## holds.

I wrote the theorem in logic as follows: ## \forall k,m \in \mathbb N . \forall f(x),g(x) \in \mathbb{F}[ x] . k = deg(f) \land m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m ##

and the skeleton for the induction proof on ## k ## would look as such:

__Induction basis__: ## k = NUMBER ## . we show ## \forall m \in \mathbb N . \forall f(x),g(x) \in \mathbb{F}[ x] . m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m ##. ( I noticed there's already some problem with my logic writing )

__Induction step:__Let ## k \geq NUMBER ## be arbitrary and suppose it is true that ## \forall m \in \mathbb N . \forall f(x),g(x) \in \mathbb{F}[ x] . m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m ##.

We'll prove that ## \forall m \in \mathbb N . \forall f(x),g(x) \in F[ x] . m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m ## (again, there is a problem with the logic since we have to prove exactly the same thing as we assumed in the induction hypothesis ).

I read that the induction is being done on the degree of ## f(x) ## which is equivalent to doing the induction on the difference between the degrees of ## f(x), g(x) ##.

**But still, how does one write in logic the theorem above so as to have it in the form of ## \forall n \in \mathbb N . P(n) ## ( where ## P(n) ## is some claim that depends on ## n ## )? and how would one write the skeleton of the induction proof?**

Last edited: