Polynomial ring and division

The chapter 4 will be devoted to understand the structure of a single variable polynomial ring $R[x]$ over a commutative unitary ring $R$. Mostly, $R$ will be taken as a field $F$, under which case $F[x]$ behaves like $\mathbb{Z}$ as a ring, so we will redo most of chapter 1 content for $F[x]$.

We start with the concrete description of elements in $R[x]$, and the concrete description of addition and multiplication.

$R[x]$ as a set

To describe the elements in $R[x]$, we just image we have a usual polynomial with variable $x$:

$$a_n{x}^n+\cdots +a_2{x}^2+a_{1}x+a_0$$

where $a_i\in R$ for all $i$. We usually represent a polynomial using $p(x)$ or $f(x)$ since polynomials have dual nature of being a function and an algebraic expression.

Zero coefficients convention

In many of previous examples and exercises, we have seen polynomials with some degree terms missing, for example, $x^3+2x+1\in \mathbb{Z}[x]$. On the surface, it does not look like a polynomial in polynomial form since $x^2$-term is missing. However, we can always add a zero coefficient to it:

$$x^3+0x^2+2x+1.$$

This is a common practice, we will state most of theorems in the form of polynomial form. When encountering a polynomial with missing degree terms, we will assume add zero coefficients to it.

Addition in $R[x]$

Now let’s formulate precisely how to add two polynomials. Let’s take two polynomials $p(x)$ and $q(x)$ in $R[x]$:

$$p(x)=a_n{x}^n+\cdots +a_2{x}^2+a_{1}x+a_0$$ $$q(x)=b_m{x}^m+\cdots +b_2{x}^2+b_{1}x+b_0$$

The expressions we have may not have the same length, let’s assume $m\le n$. We can employ the the adding zero principle to make them the same length:

$$q(x)=0_R{x}^n+\cdots +0_R{x}^{m+1}+b_m{x}^m+\cdots +b_2{x}^2+b_{1}x+b_0$$

Now we can add them together term by term, and every addition on the coefficients is done in $R$:

$$\begin{array}{rl}p(x)+q(x)& =(a_n+0_R)x^n+\cdots +(a_{m+1}+0_R)x^{m+1}\\ & +(a_m+b_m)x^m+\cdots +(a_2+b_2)x^2+(a_1+b_1)x+(a_0+b_0)\end{array}$$

Example

Add the following two polynomials in $\mathbb{Z}[x]$:

$$p(x)=2x^3+3x+1,q(x)=5x^4+7x^2+2.$$

We have:

$$\begin{array}{rl}p(x)+q(x)& =(0+5)x^4+(2+0)x^3+(0+7)x^2+(3+0)x+(1+2)\\ & =5x^4+2x^3+7x^2+3x+3.\end{array}$$

We can easily find the additive identity in $R[x]$:

Proposition

Let $R$ be a commutative unitary ring, then the additive idenntity in $R[x]$ is $0_R$.

Multiplication in $R[x]$

Again, we have two polynomials $p(x)$ and $q(x)$ in $R[x]$:

$$p(x)=a_n{x}^n+\cdots +a_2{x}^2+a_{1}x+a_0$$ $$q(x)=b_m{x}^m+\cdots +b_2{x}^2+b_{1}x+b_0$$

We can define the product of $p(x)$ and $q(x)$ as:

$$\begin{array}{rl}p(x)\cdot q(x)& =(a_n{x}^n+\cdots +a_2{x}^2+a_{1}x+a_0)(b_m{x}^m+\cdots +b_2{x}^2+b_{1}x+b_0)\\ & =a_n{b}_m{x}^{n+m}+(a_n{b}_{m-1}+a_{n-1}{b}_m)x^{n+m-1}+\cdots a_0{b}_0.\end{array}$$

To give a more concrete description, let’s consider how can we produce the coefficient of $x^k$ in the product. To get $x^k$, we need to multiply $x^i$ in $p(x)$ with $x^{k-i}$ in $q(x)$, so the coefficient of $x^k$ is:

$$\sum _{i=0}^k{a}_i{b}_{k-i}=a_0{b}_k+a_1{b}_{k-1}+\cdots +a_k{b}_0.$$

We may again use the adding zero principle to make the sum always defined.

Example

Multiply the following two polynomials in $\mathbb{Z}[x]$:

$$p(x)=2x^3+3x+1,q(x)=5x^4+7x^2+2.$$

We can list the sequence of coefficients in the result:

$$\begin{array}{rl}{x}^7& :2\ast 5=10\\ x^6& :0\\ x^5& :2\ast 7+3\ast 5=29\\ x^4& :1\ast 5=5\\ x^3& :2\ast 2+3\ast 7=25\\ x^2& :1\ast 7=7\\ x^1& :3\ast 2=6\\ x^0& :1\ast 2=2\end{array}$$

We can aggregate the coefficients together:

$$p(x)\cdot q(x)=10x^7+29x^5+5x^4+25x^3+7x^2+6x+2.$$

We can easily find the multiplicative identity in $R[x]$:

Proposition

Let $R$ be a commutative unitary ring, then the multiplicative idenntity in $R[x]$ is $1_R$.

Using the multiplication defined above, we can prove the following properties:

Theorem

Let $R$ be an integral domain, then $R[x]$ is also an integral domain.

Proof of Theorem

We will omit the proof for $R[x]$ being a commutative ring with unity, since it is straightforward. We give the proof for the zero divisor property. We choose to show the contrapositive: Suppose $p(x)\ne 0_R$ and $q(x)\ne 0_R$. We want to show $p(x)\cdot q(x)\ne 0_R$.

We can write:

$$\begin{array}{r}p(x)=a_n{x}^n+\cdots +a_2{x}^2+a_{1}x+a_0,\\ q(x)=b_m{x}^m+\cdots +b_2{x}^2+b_{1}x+b_0,\end{array}$$

where $a_n,b_m\ne 0_R$. We have:

$$\begin{array}{rl}p(x)\cdot q(x)& =(a_n{b}_m)x^{n+m}+\cdots +(a_0{b}_0)\end{array}$$

Now we find the leading term of $p(x)\cdot q(x)$ is $a_n{b}_m{x}^{n+m}$, which is non-zero since $a_n,b_m\ne 0_R$. This implies $p(x)\cdot q(x)\ne 0_R$.

Degree of a polynomial

When we write a polynomial, we usually have multiple different representations, for example:

$$p(x)=2x^3+3x+1=3x+1+2x^3=0x^4+2x^3+3x+1\in \mathbb{Z}[x].$$

In practice, we usually prefer the first form, it has two advantages:

1. All terms are in decreasing order of powers of $x$.
2. The coefficient of the highest degree term is non-zero.

There is actually a deeper reason for putting the highest power term in the front, it is related to the degree of a polynomial.

Definition

Let $p(x)=a_n{x}^n+\cdots +a_2{x}^2+a_{1}x+a_0$ be a polynomial in $R[x]$. Suppose $a_n\ne 0_R$, then the degree of $p(x)$ is defined as:

$$\mathrm{deg}(p(x))=n.$$

We define $\mathrm{deg}(0_R)=-\infty$.

With this definition, we can easily see the following properties:

Theorem

Let $R$ be a commutative unitary ring, then for all $p(x),q(x)\in R[x]$, we have:

1. $\mathrm{deg}(p(x)+q(x))\le \max (\mathrm{deg}(p(x)),\mathrm{deg}(q(x))$.
2. If $\mathrm{deg}(p(x))>\mathrm{deg}(q(x))$, then $\mathrm{deg}(p(x)+q(x))=\mathrm{deg}(p(x))$.
3. $\mathrm{deg}(p(x)\cdot q(x))\le \mathrm{deg}(p(x))+\mathrm{deg}(q(x))$.
4. If If $R$ is an integral domain, then $\mathrm{deg}(p(x)\cdot q(x))=\mathrm{deg}(p(x))+\mathrm{deg}(q(x))$.

The proof is straightforward, we will omit it. But we note that the degree will offer a good way to compare single variable polynomials.

Division algorithm in $F[x]$

Now we are ready to define the division algorithm in $F[x]$. Let’s think again why the division algorithm in $\mathbb{Z}$ works. First we need to have a good remainder condition:

$$a=bq+r,0\le r<|b|.$$

But if we ask deeper, what is the property of the set $\mathbb{Z}$ that enables us even to define the remainder condition? The answer is $\mathbb{Z}$ is a ordered set. We can compare two integers $a$ and $b$ and decide which one is bigger. The ordering is also use in the proof of division algorithm.

So to make the division algorithm work, we need to have a way to compare two polynomials. It turns out the degree is the correct choice. We can propose the following remainder condition:

$$\begin{array}{rl}f(x)& =g(x)q(x)+r(x),\\ \mathrm{deg}(r(x))& <\mathrm{deg}(g(x)).\end{array}$$

Division Algorithm for Polynomials in $F[x]$

Let $F$ be a field, then for all $f(x),g(x)\in F[x]$ with $g(x)\ne 0_F$, there exist unique polynomials $q(x),r(x)\in F[x]$ such that:

$$\begin{array}{rl}f(x)& =g(x)q(x)+r(x),\\ \mathrm{deg}(r(x))& <\mathrm{deg}(g(x)).\end{array}$$

Proof of Theorem

Existence

Let’s clear the corner cases first:

1. If $f(x)=0_F$, then we can take $q(x)=0_F$ and $r(x)=0_F$.
2. If $f(x)\ne 0_F$, but $\mathrm{deg}(f(x))<\mathrm{deg}(g(x))$, then we can take $q(x)=0_F$ and $r(x)=f(x)$.

Now suppose $\mathrm{deg}(f(x))\ge \mathrm{deg}(g(x))$. We will perform strong induction on $\mathrm{deg}(f(x))$.

Base case: $\mathrm{deg}(f(x))=0$, then based on our assumption, we have $\mathrm{deg}(g(x))\le 0$, and since $g(x)\ne 0_F$, we have $\mathrm{deg}(g(x))=0$. In this case, we know:

$$f(x)=a_0,g(x)=b_0\ne 0_F.$$

We can take $q(x)=a_0/b_0$ and $r(x)=0_F$.

Inductive step: Suppose the theorem holds for all polynomials with degree less than $n$. Now we consider a polynomial $f(x)$ with $\mathrm{deg}(f(x))=n$, and $g(x)$ with $\mathrm{deg}(g(x))=m$, we can write:

$$\begin{gathered} f(x)=a_n{x}^n+\cdots +a_2{x}^2+a_{1}x+a_0, \\ g(x)=b_m{x}^m+\cdots +b_2{x}^2+b_{1}x+b_0, \end{gathered}$$

where $a_n\ne 0_F$ and $b_m\ne 0_F$. We will try to get the leading term of $f(x)$ out of the way. We can do this by subtracting a multiple of $g(x)$ from $f(x)$:

$$\begin{array}{rl}f(x)-a_n{b_m}^{-1}{x}^{n-m}g(x)=& a_n{x}^n-a_n{b_m}^{-1}{x}^{n-m}{b}_m{x}^m+L.O.T.\\ =& L.O.T.\end{array}$$

Here $L.O.T.$ stands for lower order terms. We can see that the degree of

$$f(x)-a_n{b_m}^{-1}{x}^{n-m}g(x)$$

is less than $n$. We will have three possibilities:

Firstly, if $L.O.T.=0_F$, then we can take $q(x)=a_n{b_m}^{-1}{x}^{n-m}$ and $r(x)=0_F$, and we are done.

Secondly, suppose we have $\mathrm{deg}(f(x)-a_n{b_m}^{-1}{x}^{n-m}g(x))<\mathrm{deg}(g(x))$, then we are in the corner case 2, and we can take $q(x)=a_n{b_m}^{-1}{x}^{n-m}$ and $r(x)=f(x)-a_n{b_m}^{-1}{x}^{n-m}g(x)$, we have:

$$f(x)-a_n{b_m}^{-1}{x}^{n-m}g(x)=q(x)g(x)+r(x),\mathrm{deg}(r(x))<\mathrm{deg}(g(x)),$$

and we are done.

Finally, f $\mathrm{deg}(f(x)-a_n{b_m}^{-1}{x}^{n-m}g(x))\ge \mathrm{deg}(g(x))$, then we can apply the inductive hypothesis.

By the inductive hypothesis, we can also find polynomials $q(x)$ and $r(x)$ such that:

$$\begin{array}{rl}f(x)-a_n{b_m}^{-1}{x}^{n-m}g(x)& =q(x)g(x)+r(x),\\ \mathrm{deg}(r(x))& <m.\end{array}$$

In both cases, we can rearrange the equation to get:

$$f(x)=(q(x)+a_n{b_m}^{-1}{x}^{n-m})g(x)+r(x).$$

This gives us the existence of $q(x)$ and $r(x)$.

Uniqueness

Suppose we have two distinct pairs $(q_1(x),r_1(x))$ and $(q_2(x),r_2(x))$ that satisfy the theorem. We can write:

$$\begin{array}{rl}f(x)& =g(x)q_1(x)+r_1(x),\\ f(x)& =g(x)q_2(x)+r_2(x).\end{array}$$

We first notice that $q_1(x)\ne q_2(x)$ and $r_1(x)\ne r_2(x)$.

We can subtract the two equations to get:

$$\begin{array}{rl}{0}_F& =g(x)(q_1(x)-q_2(x))+(r_1(x)-r_2(x)).\end{array}$$

Since $g(x)\ne 0_F$, we know:

$$\begin{array}{rl}\mathrm{deg}(g(x)(q_1(x)-q_2(x)\left)\right)& =\mathrm{deg}(q_1(x)-q_2(x))+\mathrm{deg}(g(x))\\ & \ge \mathrm{deg}(g(x))>\max (\mathrm{deg}(r_1(x)),\mathrm{deg}(r_2(x)))\\ & \ge \mathrm{deg}(r_1(x)-r_2(x)).\end{array}$$

Now since $r_1(x)-r_2(x)\ne 0_F$, we have:

$$\mathrm{deg}(r_1(x)-r_2(x))\ge 0.$$

This results in:

$$\begin{array}{rl}\mathrm{deg}(g(x)(q_1(x)-q_2(x))+(r_1(x)-r_2(x)\left)\right)& >\mathrm{deg}(r_1(x)-r_2(x))\ge 0,\end{array}$$

which is a contradiction, since we have

$$0_F=g(x)(q_1(x)-q_2(x))+(r_1(x)-r_2(x)).$$

$■$

Warning

It is important to note that the division algorithm is only guaranteed to work in a coefficient field $F$. $\mathbb{Z}[x]$ does not have the division algorithm, since $\mathbb{Z}$ is not a field.