# Induction proof of Polynomial Division Theorem

• Simple Induction
CGandC
Theorem: 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.
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.​

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:
Delta2

Mentor
2022 Award
Theorem: 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.
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.​

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.
This is correct and the given induction is a bit clumsy. You can set the base for ##k=0.##

Or you can do a case distinction first: For ##k<m## there is nothing to do, because we can set ##q(x)=0## and ##r(x)=f(x)##.

Now we are left with ##k\geq m \geq 1.## Then an induction base ##k=m## would be reasonable. However, all the following lines are the same as for the case ##k>m## so we would actually write them twice.

The induction step is needed at the end because we decreased the degree of ##f(x)## by possibly only ##1,## so ##\deg (f(x)-h(x))## could still be greater than ##m## and we need the induction step as written.

In a case like this, where we reduce the degree until ##k<m,## we could simply say "and so on until the degree of ##f(x)-h_1(x)-h_2(x)-h_{k-m}(x)## is smaller than ##m.##"

It is not really an induction since our process is going down and we have a lower bound, i.e. we have an algorithm that surely comes to an end.

Another way to prove such theorems is by indirect proof and the assumption of a least counterexample:

Assume that ##f(x)## with ##k\geq m## is a counterexample where we cannot find ##r(x)## and ##q(x)## and of minimal degree of all counterexamples. We already know that ##k\geq m## because otherwise we had found such polynomials: ##r(x)=f(x)\, , \,q(x)=0.## Now do the step as written in the lecture note. Then either ##f(x)## is no counterexample (contradiction to the assumption), or ##f(x)-h(x)## is also a counterexample, but of less degree (contradiction to minimality).

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?

Delta2 and CGandC
Gold Member
Maybe OP can do some reading on Strong and Weak forms of Induction.

Delta2
CGandC
It is not really an induction since our process is going down and we have a lower bound, i.e. we have an algorithm that surely comes to an end.
If I have to prove a theorem of the form ## P(0) \land \forall n \in \mathbb N . ( P(n+1) \rightarrow P(n) ) ## , note that what immediately pops into mind is a proof by induction, but it is sort of a reverse induction since in the induction step we would assume ## P(n+1) ## and we'd prove ## P(n) ##. What's this kind of induction called? recursion? dynamic programming?
Another way to prove such theorems is by indirect proof and the assumption of a least counterexample:

I'd prove the theorem by separating to cases as follows:

Assume ## k < m ## , [ rest of the proof of theorem goes here ]
Assume ## k \geq m ## , [ rest of the proof of theorem goes here ]

Maybe OP can do some reading on Strong and Weak forms of Induction.

I'm familiar with these inductions but the proof by induction of the theorem I brought is a little bit weird, When proving by induction, I'm used to have a theorem to prove as such: ## P(0) \land \forall n \in \mathbb N . ( P(n) \rightarrow P(n+1) ) ##, where the base case to prove is ## P(0) ## , the induction step is assuming arbitrary ## n \in \mathbb N ## and P(n), then I've to prove ## P(n+1) ##.
But I couldn't formalize the theorem according to logic with quantifiers so as to see how I could apply the induction in a way that resembles proving theorems of the form ## P(0) \land \forall n \in \mathbb N . ( P(n) \rightarrow P(n+1) ) ##, what would the logical formalization of the theorem be in order to clearly see how I could apply weak/strong induction?

SSequence
Just commenting on the logical form for the statement/theorem you have written [not commenting on the other parts since I haven't encountered the proof for the given statement before and I would have to spend fair amount of time reading that in OP], I don't understand how you have written it.

For example, here is the theorem (from OP):
Theorem: 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.
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) ##

and the corresponding logical form from OP:
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:
Here is my take on this:
##\forall f,g \in \mathbb{F} \,\,[ \,\, deg(g) \geq 1 \rightarrow [\exists q , r \in \mathbb{F} \,\, [(deg(r)<deg(g)) ##
##\land \forall x \in \mathbb{R} (f(x)=q(x) \cdot g(x)+r(x)) ] \,] \,\, ] ##
Edit: Noticed some issues with single line display (probably due to long length), so I split it into two separate lines

The usage of "and" instead of "or" is based upon wikipedia statement of the theorem:
https://en.wikipedia.org/wiki/Polynomial_remainder_theorem

Above I have assumed ##\mathbb{F}## to denote the set of polynomials. Also, the above formula doesn't cover uniqueness of ##q## and ##r## (it seems that would make the logical formula really long), only their existence.

Last edited:
CGandC and Delta2
CGandC
Here is my take on this:
##\forall f,g \in \mathbb{F[ x]} \,\,[ \,\, deg(g) \geq 1 \rightarrow [\exists q , r \in \mathbb{F} \,\, [(deg(r)<deg(g)) ##
##\land \forall x \in \mathbb{R} (f(x)=q(x) \cdot g(x)+r(x)) ] \,] \,\, ] ##
Do you have any idea how a proof by induction would work on this theorem? ( I can't see it simply as a claim of the form ## P(0) \land \forall n \in \mathbb N . ( P(n+1) \rightarrow P(n) ) ## ). Instead of the base case being ## k < m ##, I would expect base case such as ## k = \_ ## , and instead of an induction step of ## m \leq k ## I would expect induction step beginning with " Let ## k \geq \_ ## be arbitrary ... " . The answer by @fresh_42 above helped but I still feel unsure as to how the induction happens or whether the proof is using a different technique that resembles induction.

Mentor
2022 Award
Do you have any idea how a proof by induction would work on this theorem? ( I can't see it simply as a claim of the form ## P(0) \land \forall n \in \mathbb N . ( P(n+1) \rightarrow P(n) ) ## ). Instead of the base case being ## k < m ##, I would expect base case such as ## k = \_ ## , and instead of an induction step of ## m \leq k ## I would expect induction step beginning with " Let ## k \geq \_ ## be arbitrary ... " . The answer by @fresh_42 above helped but I still feel unsure as to how the induction happens or whether the proof is using a different technique that resembles induction.

Induction:

Deal with the case ##k<m##.
Take ##P(k)=P(m)## as induction base.
Prove ##P(k+1) \longrightarrow P(k)##.

Algorithm:

DO WHILE ##k\geq m##
##P(k+1) \longrightarrow P(k)##
Store ##h(x)##
and prove that the degree has strictly decreased
END DO
Deal with ##k<m##.
Use all ##h(x)## to write down the final ##q(x)## and ##r(x)##.

Indirect proof:

Let ##k## be a minimal counterexample, i.e. there is no way to write ##f(x)=q(x)\cdot g(x)+r(x)## with ##\deg r(x) <\deg(g(x)##. Then ##f(x)-h(x)=q_0(x)g(x)+r(x)## and ##\deg (f(x)-h(x))<k##. Since ##k## was minimal, we have ##\deg r(x)\geq \deg g(x)## contradicting our construction of ##r(x).##

CGandC
CGandC
I had a small mistake in the theorem I was trying to prove, I had to prove:
Theorem: Let ## f(x),g(x) \in \mathbb{F}[ x] ## be polynomials, s.t. ## deg( g ) \geq 1 ## . Then, there exist unique polynomials ## q(x),r(x) \in \mathbb{F}[ x] ## s.t.
## f(x)=q(x)⋅g(x)+r(x) ## and ## r(x) = 0 or deg(r) < deg(g) ##

In logic, one can write this theorem as:
## \forall f(x),g(x) \in \mathbb{F}[ x]. deg( g ) \geq 1 . \exists q(x),r(x) \in \mathbb{F}[ x]. f(x)=q(x)⋅g(x)+r(x) \land ( r(x) = 0 \lor deg(r)< deg(g) ) ##

( I think the theorem above has a version for uniqueness too for the polynomials ## q(x),r(x) ##, but I'll prove the current version without uniqueness)

My proof attempt:
Let ## g(x) \in F[ x] ## be arbitrary where ## x ## is an indeterminate. Suppose ## deg(g) \geq 1 ##. Denote ## deg(g) = m ##. There exist ## b_0,...,b_m \in \mathbb{F} ## s.t. ## g(x) = b_0 + ... + b_m \cdot x^m ##. We'll prove the following claim by Strong-induction on ## deg(f) ##,
## \forall f(x) \in \mathbb{F}[ x]. \exists q(x),r(x) \in \mathbb{F}[ x]. f(x)=q(x)⋅g(x)+r(x) \land ( r(x) = 0 \lor deg(r)< deg(g) ) ##,
Base case: ## f = 0 ##. We'll chose ## q(x) = 0, r(x) = 0 ## and we're finished.
Induction step: Let ## f(x) \in \mathbb{F}[ x] ## be arbitrary. Denote ## deg(f) = n ##. There exist ## a_0,...,a_n \in \mathbb{F} ## s.t. ## f(x) = a_0 + ... + a_n \cdot x^n ##.
( induction assumption: ) Suppose that ## \forall \hat{f}(x) \in \mathbb{F}[ x] . deg( \hat{f} ) < n . \exists q(x),r(x) \in \mathbb{F}[ x]. \hat{f}(x)=q(x)⋅g(x)+r(x) \land ( r(x) = 0 \lor deg(r)< deg(g) ) ##.
We'll prove that ## \exists q(x),r(x) \in \mathbb{F}[ x]. f(x)=q(x)⋅g(x)+r(x) \land ( r(x) = 0 \lor deg(r)< deg(g) ) ##.
If ## n < m ## then we'll chose ## r = f , q = 0 ## and we'll have ## f(x) = 0 \cdot g(x) + f(x) = f(x) ## and we're finished.
If ## n \geq m ## then we'll look at ## h(x) = \frac{a_n}{b_m} \cdot x^{n-m} \cdot g(x) ##, notice that ## deg( f - h) < n ## and from the induction assumption there exist ## q(x),r(x) \in \mathbb{F}[ x] ## s.t. ## f(x) - h(x) = q(x) \cdot g(x) + r(x) ##, meaning ## f(x) = q(x) \cdot g(x) + h(x) + r(x) =q(x) \cdot g(x) + ( \frac{a_n}{b_m} \cdot x^{n-m} \cdot g(x) ) + r(x) ##
## = ( q(x) + \frac{a_n}{b_m} \cdot x^{n-m} )\cdot g(x) + r(x) ## and we're finished.

What do you think? ( The induction assumption was only used in the case ## n \geq m ## )

fresh_42
Mentor
2022 Award
What do you think?
Looks correct. I couldn't see a mistake.

Uniqueness is in general not necessary. It could be tricky to prove. From
$$f(x)=q(x)g(x)+r(x)=p(x)g(x)+s(x) \Longrightarrow (p(x)-q(x))g(x)+(s(x)-r(x))=0$$
we only get that the highest coefficients of ##p(x)## and ##q(x)## are equal. I'm not sure whether induction works since the coefficients less than ##m=\operatorname{deg}g## could be anything.

More interesting than uniqueness are the cases in which we haven't a field, rather only a ring with a valuation function.

Last edited:
CGandC
Here is a proof for uniqueness ( no need for induction here ):

[ We proved existence of ## q ,r \in \mathbb{F}[ x] ## s.t. ## f(x) = q(x) \cdot g(x) + r(x) ## where ## r = 0 ## or ## deg(r) < deg(g) ## ]
Let ## p(x), s(x) \in \mathbb{F} [ x] ## be arbitrary such that ## f(x) = p(x) \cdot g(x) + s(x) ##.
We have that ## f(x) = q(x) \cdot g(x) + r(x) = p(x) \cdot g(x) + s(x) \Longrightarrow (p(x)-q(x))g(x) = (r(x)-s(x)) ##.
If ## p - q \neq 0 ## then the polynomial ## (p(x)-q(x))g(x) ## has degree higher or equal to ## g(x) ##, whilst note that the polynomial ## (r(x)-s(x)) ## is either zero or has degree less than ## g(x) ##, hence in the equation ## (p(x)-q(x))g(x) = (r(x)-s(x)) ## we get a contradiction since the left-hand side is a polynomial with degree higher than the righthand side. Hence ## p = q ##. This means that ## r = s ## and we're finished.

Mentor
2022 Award
Here is a proof for uniqueness ( no need for induction here ):

[ We proved existence of ## q ,r \in \mathbb{F}[ x] ## s.t. ## f(x) = q(x) \cdot g(x) + r(x) ## where ## r = 0 ## or ## deg(r) < deg(g) ## ]
Let ## p(x), s(x) \in \mathbb{F} [ x] ## be arbitrary such that ## f(x) = p(x) \cdot g(x) + s(x) ##.
We have that ## f(x) = q(x) \cdot g(x) + r(x) = p(x) \cdot g(x) + s(x) \Longrightarrow (p(x)-q(x))g(x) = (r(x)-s(x)) ##.
If ## p - q \neq 0 ## then the polynomial ## (p(x)-q(x))g(x) ## has degree higher or equal to ## g(x) ##, whilst note that the polynomial ## (r(x)-s(x)) ## is either zero or has degree less than ## g(x) ##, hence in the equation ## (p(x)-q(x))g(x) = (r(x)-s(x)) ## we get a contradiction since the left-hand side is a polynomial with degree higher than the righthand side. Hence ## p = q ##. This means that ## r = s ## and we're finished.
From ##p-q\neq 0## and the degree consideration, we can only conclude that the leading terms in ##p## and ##q## are equal so that they vanish. I do not see why the lower terms should be equal, too.