Polynomial ring/Field/Euclidean division/2/Introduction/Section

Definition

Let ${}K$ be a field. We say that a polynomial ${}T\in K[X]$ divides a polynomial ${}P\in K[X]$, if there exists a polynomial ${}Q\in K[X]$ such that

${}P=TQ\,.$

If ${}P$ can be divided by ${}T$, we also say that ${}P$ is a multiple of ${}T$. In ${}K[X]$ it is not possible to divide any element by any element ${}\neq 0$. This is different from a field, but similar no the integers ${}\mathbb {Z}$. However, there is an important substitute, the Euclidean division.

Theorem

Let ${}K$ be a field and let ${}K[X]$ be the polynomial ring over ${}K$. Let ${}P,T\in K[X]$ be polynomials with ${}T\neq 0$. Then there exist unique polynomials ${}Q,R\in K[X]$ such that

$P=TQ+R{\text{ and with }}\operatorname {deg} \,(R)<\operatorname {deg} \,(T){\text{ or }}R=0.$

Proof

We prove the statement about the existence by induction over the degree of ${}P$. If the degree of ${}T$ is larger than the degree of ${}P$, then ${}Q=0$ and ${}R=P$ is a solution.

Suppose that ${}\operatorname {deg} \,(P)=0$. By the remark just made also ${}\operatorname {deg} \,(T)=0$ holds, so ${}T$ is a constant polynomial, and therefore (since ${}T\neq 0$ and ${}K$ is a field) ${}Q=P/T$ and ${}R=0$ is a solution.

So suppose now that ${}\operatorname {deg} \,(P)=n$ and that the statement for smaller degrees is already proven. We write ${}P=a_{n}X^{n}+\cdots +a_{1}X+a_{0}$ and ${}T=b_{k}X^{k}+\cdots +b_{1}X+b_{0}$ with ${}a_{n},b_{k}\neq 0,\,k\leq n$. Then setting ${}H={\frac {a_{n}}{b_{k}}}X^{n-k}$ we have the relation

${}{\begin{aligned}P'&:=P-TH\\&=0X^{n}+{\left(a_{n-1}-{\frac {a_{n}}{b_{k}}}b_{k-1}\right)}X^{n-1}+\cdots +{\left(a_{n-k}-{\frac {a_{n}}{b_{k}}}b_{0}\right)}X^{n-k}+a_{n-k-1}X^{n-k-1}+\cdots +a_{0}.\end{aligned}}$

The degree of this polynomial ${}P'$ is smaller than ${}n$ and we can apply the induction hypothesis to it. That means there exist ${}Q'$ and ${}R'$ such that

$P'=TQ'+R'{\text{ and with }}\operatorname {deg} \,(R')<\operatorname {deg} \,(T){\text{ or }}R'=0.$

From this we get altogether

${}P=P'+TH=TQ'+TH+R'=T(Q'+H)+R'\,,$

so that ${}Q=Q'+H$ and ${}R=R'$ is a solution.

To prove uniqueness, let ${}P=TQ+R=TQ'+R'$, both fulfilling the stated conditions. Then ${}T(Q-Q')=R'-R$. Since the degree of the difference ${}R'-R$ is smaller than ${}\operatorname {deg} \,(T)$, this implies ${}R=R'$ and so ${}Q=Q'$.

$\Box$

The polynomial ${}T$ divides ${}P$ if and only if the remainder in the Euclidean division is ${}0$. The proof of this theorem is constructive, that is, it describes a method how to perform the Euclidean division effectively. For this, it is necessary to be able to perform the operations in the base field. We give two examples, one over the rational numbers and one over the complex numbers.

Example

We want to apply the Euclidean division (over ${}\mathbb {Q}$)

$P=6X^{3}+X+1{\text{ divided by }}T=3X^{2}+2X-4.$

So we want to divide a polynomial of degree ${}3$ by a polynomial of degree ${}2$, hence the quotient and also the remainder have (at most) degree ${}1$. For the first step, we ask with which term we have to multiply ${}T$ to achieve that the product and ${}P$ have the same leading term. This is ${}2X$. The product is

${}2X{\left(3X^{2}+2X-4\right)}=6X^{3}+4X^{2}-8X\,.$

The difference between ${}P$ and this product is

${}6X^{3}+X+1-{\left(6X^{3}+4X^{2}-8X\right)}=-4X^{2}+9X+1\,.$

We continue the division by ${}T$ with this polynomial, which we call ${}P'$. In order to get coincidence with the leading coefficient we have to multiply ${}T$ with ${}{\frac {-4}{3}}$. This yields

${}-{\frac {4}{3}}T=-{\frac {4}{3}}{\left(3X^{2}+2X-4\right)}=-4X^{2}-{\frac {8}{3}}X+{\frac {16}{3}}\,.$

The difference between this and ${}P'$ is therefore

${}-4X^{2}+9X+1-{\left(-4X^{2}-{\frac {8}{3}}X+{\frac {16}{3}}\right)}={\frac {35}{3}}X-{\frac {13}{3}}\,.$

This is the remainder and altogether we get

${}6X^{3}+X+1={\left(3X^{2}+2X-4\right)}{\left(2X-{\frac {4}{3}}\right)}+{\frac {35}{3}}X-{\frac {13}{3}}\,.$

Example

We perform the Euclidean division

$P=(4+3{\mathrm {i} })X^{3}+X^{2}+5{\mathrm {i} }{\text{ divided by }}T=(1+{\mathrm {i} })X^{2}+X-3+2{\mathrm {i} }.$

The inverse of ${}1+{\mathrm {i} }$ is ${}{\frac {1}{2}}-{\frac {1}{2}}{\mathrm {i} }$, and therefore we have

${}{\begin{aligned}(4+3{\mathrm {i} })(1+{\mathrm {i} })^{-1}&=(4+3{\mathrm {i} }){\left({\frac {1}{2}}-{\frac {1}{2}}{\mathrm {i} }\right)}\\&=2+{\frac {3}{2}}-2{\mathrm {i} }+{\frac {3}{2}}{\mathrm {i} }\\&={\frac {7}{2}}-{\frac {1}{2}}{\mathrm {i} }.\end{aligned}}$

Hence, ${}Q$ starts with ${}{\left({\frac {7}{2}}-{\frac {1}{2}}{\mathrm {i} }\right)}X$, and we have

${}{\begin{aligned}((1+{\mathrm {i} })X^{2}+X-3+2{\mathrm {i} }){\left({\frac {7}{2}}-{\frac {1}{2}}{\mathrm {i} }\right)}X&=(4+3{\mathrm {i} })X^{3}+{\left({\frac {7}{2}}-{\frac {1}{2}}{\mathrm {i} }\right)}X^{2}+{\left(-{\frac {19}{2}}+{\frac {17}{2}}{\mathrm {i} }\right)}X\\\end{aligned}}$

We have to subtract this term from ${}P$ and we obtain

${}{\begin{aligned}P-{\left((4+3{\mathrm {i} })X^{3}+{\left({\frac {7}{2}}-{\frac {1}{2}}{\mathrm {i} }\right)}X^{2}+{\left(-{\frac {19}{2}}+{\frac {17}{2}}{\mathrm {i} }\right)}X\right)}&={\left(-{\frac {5}{2}}+{\frac {1}{2}}{\mathrm {i} }\right)}X^{2}+{\left({\frac {19}{2}}-{\frac {17}{2}}{\mathrm {i} }\right)}X+5{\mathrm {i} }\\\,\end{aligned}}$

We apply the same procedure to this polynomial (which we call ${}P'$). We compute

${}{\begin{aligned}{\left(-{\frac {5}{2}}+{\frac {1}{2}}{\mathrm {i} }\right)}{\left({\frac {1}{2}}-{\frac {1}{2}}{\mathrm {i} }\right)}&=-1+{\frac {3}{2}}{\mathrm {i} }\\\end{aligned}}$

Therefore, the constant term of ${}Q$ equals ${}-1+{\frac {3}{2}}{\mathrm {i} }$, and we obtain

${\left((1+{\mathrm {i} })X^{2}+X-3+2{\mathrm {i} }\right)}{\left(-1+{\frac {3}{2}}{\mathrm {i} }\right)}={\left(-{\frac {5}{2}}+{\frac {1}{2}}{\mathrm {i} }\right)}X^{2}+{\left(-1+{\frac {3}{2}}{\mathrm {i} }\right)}X-{\frac {13}{2}}{\mathrm {i} }\,.$

We subtract this from ${}P'$ and get

${}P'-{\left({\left(-{\frac {5}{2}}+{\frac {1}{2}}{\mathrm {i} }\right)}X^{2}+{\left(-1+{\frac {3}{2}}{\mathrm {i} }\right)}X-{\frac {13}{2}}{\mathrm {i} }\right)}={\left({\frac {21}{2}}-10{\mathrm {i} }\right)}X+{\frac {23}{2}}{\mathrm {i} }\,.$

This term is the remainder ${}R$, the Euclidean division altogether is

${}{\begin{aligned}(4+3{\mathrm {i} })X^{3}+X^{2}+5{\mathrm {i} }&=((1+{\mathrm {i} })X^{2}+X-3+2{\mathrm {i} }){\left({\left({\frac {7}{2}}-{\frac {1}{2}}{\mathrm {i} }\right)}X-1+{\frac {3}{2}}{\mathrm {i} }\right)}+{\left({\frac {21}{2}}-10{\mathrm {i} }\right)}X+{\frac {23}{2}}{\mathrm {i} }\\\,\end{aligned}}$