# Euclidean Division of Polynomials Proof

I am tasked with the following:

Proposition (Euclidean Division of Polynomials): Let $$A,B \in \mathbb{R}[X]$$ be nonzero. There exists a unique pair $$(Q,R) \in \mathbb{R}[X]^2$$ such that: $$A=BQ+R,\;\;\;\;\;\;\;\;\;\deg R<\deg B.$$

I actually have a proof but I need someone to check it for me.

$$\mathbf{Proof\;of\;the\;Uniqueness:}$$ Let $$A(x)$$ and $$B(x) \in \mathbb{R}$$ be nonzero, let $$(Q_1,R_1), (Q_2,R_2)$$ such that $$A=Q_1B+R_1=Q_2B+R_2$$. we will prove this is not possible. first we see that $$B(Q_1-Q_2)=R_2-R_1$$ We have $$\deg(R_2-R_1)<\deg B$$, because $$\deg R_2<\deg B$$ and $$\deg R_1<\deg B$$ so $$\deg R_2-R_1=\max(\deg R_1,\deg R_2)<\deg B$$. but $$B(Q_1-Q_2)=R_2-R_1$$, then $$\deg B(Q_1-Q_2)<\deg B$$ which is false, except if $$Q_1-Q_2=0$$. But if $$Q_1-Q_2=0$$, then $$R_2-R_1=0$$. $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\square$$ $$\mathbf{Proof\;of\;the\;Existence:}$$ We will prove this by induction on the degree of $$A$$. Let $$P(X)$$ be the statement "$$A=BQ+R:\deg A=x$$ and $$\deg R<\deg B$$' $$P(0)$$ that is when $$\deg A=0$$, we have $$\\$$ $$A=0.B+R$$ where $$R=A$$ ,$$\deg R=0<\deg B$$ Assume P is true for $$A$$ with degree less than $$N>0$$, then we have $$A=BQ+R, \deg R<\deg B,\;\deg A Consider $$a$$ such that $$\deg A=N+1$$ $$\\$$ we have the monomial $$a_{N+1}X^{N+1}$$, but there exists a $$P \in \mathbb{R}[X]$$ such that $$\deg P=h$$ and has the monomial $$p_hX^h$$, such that for the monomial $$b_kX^k$$ in $$B$$, $$(p_hX^h)(b_kX^k)=p_hb_kX^{h+k}=a_{N+1}X^{N+1}$$ Then we have $$A-BP=a_{N+1}X^{N+1}+...+a_0\;$$-$$[p_hb_kX^{h+k}+...+b_0(p_hX^h+...+p_0)]$$ (I have skipeed some steps because this is tiring), but $$p_hb_kX^{h+k}=a_{N+1}X^{N+1}$$, therefore $$A-BP=a_NX^N+...+a_0+...+b_0(p_hX^h+...+P_0)$$ We see that $$\deg(A-BP)\le N$$, Hence the division exists for $$A-BP$$. $$\\$$We have $$A-BP=BP+(A-2BP)$$ and $$\deg(A-2BP)<\deg B$$, but $$\deg(A-2BP)=\deg(A-BP)<\deg B$$  Thus, we have $$\\$$ $$A=BP+(A-BP)$$ with $$\deg A=N+1$$ and $$\deg(A-BP)<\deg B$$. We have proved $$P(0)$$ and if $$P(N)$$ is true then $$P(N+1)$$ is true, therefore by the principle of induction, $$P$$ is true for all $$N \in \mathbb{N}$$.$$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$$ $$\square$$ Phew, writing that was harder than the proof. I have skipped some details because this is getting tiring and long, but please let me know what you think.

• Do note that the statement of the proposition should be "$deg(R)< deg(B) \text{ or } R=0$" rather than just "$deg(R)<deg(B)$". Otherwise you are not taking into account when $deg(B)=0$. In your proof, you should also deal with this case. Nov 24, 2019 at 21:32
• @parafoo maybe OP defines the degree of the zero polynomial to be say $-\infty$. Nov 24, 2019 at 22:44
• @YiFan Oh yes that might be it. Nov 24, 2019 at 22:48
• @parafoo But I have A and B defined to be nonzero polynomials so it does take R=0 into account Nov 25, 2019 at 5:07

Since you are trying to prove the $$n+1^{\text{th}}$$ case, your inductive hypothesis should read "Assume $$P$$ is true for all $$A$$ with degree less than or equal to $$n$$" rather than just assuming it for degree less than $$n$$.
In your paragraph after the inductive hypothesis, you have not dealt with the case where the degree of $$B$$ is larger than the degree of $$A$$. In this case, it would not be possible to find such a $$P$$ that you have specified. This is easily rectified by observing that $$A = B(0)+A$$ since $$\text{deg}(A)<\text{deg}(B)$$.
You have not shown $$\text{deg}(A-2BP) < \text{deg}(B)$$. In fact, this statement is not true in general. What you should do instead is to use your inductive hypothesis on $$A-BP$$ since $$\text{deg}(A-BP) \leq n$$. This will give you that $$A-BP = BQ+R$$ for some $$Q,R \in \mathbb{R}[x]$$ where $$\text{deg}(R) < \text{deg}(B)$$. Adding $$BP$$ to both sides will get what you want.