Polynomials/Field/Euclidean division/Introduction/Section

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 computation of the polynomials ${}Q$ and ${}R$ is also called long division. The polynomial ${}T$ is a factor of ${}P$ if and only if the division of ${}P$ by ${}T$ yields the remainder ${}0$. The proof of this theorem is constructive, meaning it can be used to do the computation effectively. For this, one has to be able to do the computing operations in the field ${}K$. We give an example.

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}}\,.$

Lemma

Let ${}K$ be a field and let ${}K[X]$ be the polynomial ring over ${}K$. Let ${}P\in K[X]$ be a polynomial and ${}a\in K$. Then ${}a$ is a zero of ${}P$ if and only if ${}P$ is a multiple of the linear polynomial ${}X-a$.

Proof

If ${}P$ is a multiple of ${}X-a$, then we can write

${}P=(X-a)Q\,$

with another polynomial ${}Q$. Inserting ${}a$ yields

${}P(a)=(a-a)Q(a)=0\,.$

In general, there exists, due to fact, a representation

${}P=(X-a)Q+R\,,$

where either ${}R=0$ or the degree of ${}R$ is ${}0$, so in both cases ${}R$ is a constant. Inserting ${}a$ yields

${}P(a)=R\,.$

So if ${}P(a)=0$ holds, then the remainder must be ${}R=0$, and this means ${}P=(X-a)Q$.

$\Box$

Corollary

Let ${}K$ be a field and let ${}K[X]$ be the polynomial ring over ${}K$. Let ${}P\in K[X]$ be a polynomial (${}\neq 0$) of degree ${}d$. Then ${}P$ has at most ${}d$ zeroes.

Proof

We prove the statement by induction over ${}d$. For ${}d=0,1$ the statement holds. So suppose that ${}d\geq 2$ and that the statement is already proven for smaller degrees. Let ${}a$ be a zero of ${}P$ (if ${}P$ does not have a zero at all, we are done anyway). Hence, ${}P=Q(X-a)$ by fact and the degree of ${}Q$ is ${}d-1$, so we can apply to ${}Q$ the induction hypothesis. The polynomial ${}Q$ has at most ${}d-1$ zeroes. For ${}b\in K$ we have ${}P(b)=Q(b)(b-a)$. This can be zero, due to fact, only if one factor is ${}0$, so the zeroes of ${}P$ are ${}a$ or a zero of ${}Q$. Hence, there are at most ${}d$ zeroes of ${}P$.

$\Box$