Unit roots/Divisibility of polynomials

This chapter demonstrates the use of unit roots in problems of divisibility of polynomials.

Divisibility of polynomials

Let $f(x)$ and $p(x)$ be two polynomials.

Assume that there is another polynomial $q(x)$, such that:

$f(x)=p(x)\cdot q(x)$.

If $f(x)$, $p(x)$ and $q(x)$ are polynomials with integer coefficients, then, $f(x)$ is said to be divisible by $p(x)$ over the integers.

Similarly, if $f(x)$, $p(x)$ and $q(x)$ are polynomials with rational coefficients, then, $f(x)$ is said to be divisible by $p(x)$ over the rational numbers.

If $f(x)$, $p(x)$ and $q(x)$ are polynomials with real coefficients or complex coefficients, then, $f(x)$ is said to be divisible by $p(x)$ over the real numbers or the complex numbers.

Example 1 Let $f(x)=x^2-1$ and $p(x)=2x+2$. The coefficients of these two polynomials are integers. However:

$x^2-1=(2x+2)(\frac{1}{2}x-\frac{1}{2})$.

The polynomial in the second bracket of the right hand side $\frac{1}{2}x-\frac{1}{2}$ does not have integer coefficients. Therefore, $f(x)$ is not divisible by $p(x)$ over the integers.

However, if we consider that $f(x)$ and $p(x)$ are polynomials with rational, real, or complex coefficients, then $\frac{1}{2}x-\frac{1}{2}$ is also a polynomial with rational, real, or complex coefficients. So, $f(x)$ is divisible by $p(x)$ over the rational numbers, the real numbers, or the complex numbers. QED

Therefore, the divisibility of polynomials is highly associated with the set of numbers that we allow the coefficients to take. However, as both $f(x)$ and $p(x)$ are known polynomials, the coefficients of the quotient $q(x)$ is key to the divisibility.

Now, let $f(x)=p(x)\cdot q(x)$, where $f(x)$ and $p(x)$ have coefficients in the set of numbers we have specified. How can we determine whether $q(x)$ is also a polynomial with coefficients in the same set? The answer of this question is given in the following rule:

Rule 1 Let $f(x)=p(x)\cdot q(x)$.

• If $f(x)$ and $p(x)$ have complex coefficients, then $q(x)$ has complex coefficients. $f(x)$ is divisible by $p(x)$ over the complex numbers.
• If $f(x)$ and $p(x)$ have real coefficients, then $q(x)$ has real coefficients. $f(x)$ is divisible by $p(x)$ over the real numbers.
• If $f(x)$ and $p(x)$ have rational coefficients, then $q(x)$ has rational coefficients. $f(x)$ is divisible by $p(x)$ over the rational numbers.
• If $f(x)$ and $p(x)$ have integer coefficients, and (sufficiently by not necessarily) $p_0=1$ then $q(x)$ has integer coefficients. $f(x)$ is divisible by $p(x)$ over the integers.

This rule is proved in the appendix.

When we consider only integer coefficients, the condition $p_0=1$ is not necessary. For example, let $f(x)=2x^2-2$ and $p(x)=-2x+2$, then $p_0=-2$ but $2x^2-2=(-2x+2)(-x-1)$.

Factor theorem and unit roots

In elementary algebra, we have the remainder theorem. It is stated here without an accompanying proof:

Remainder theorem The remainder of the division of a polynomial $f(x)$ by $x-a$ equals $f(a)$.

From this theorem we can have the following result, commonly called the "factor theorem":
Factor theorem A polynomial $f(x)$ is divisible by $x-a$, if and only if $f(a)=0$.
(Note that $f(x)$ and $a$ are known, and we automatically assume that it falls in the set of numbers over which divisibility is considered.)

Proof Suppose $f(x)$ is divisible by $x-a$, then the remainder of the division of a polynomial $f(x)$ by $x-a$ equals zero. So, $f(a)=0$.
On the other hand, if $f(a)=0$, then the remainder of the division of a polynomial $f(x)$ by $x-a$ equals zero. So, $f(x)=(x-a)q(x)$. Moreover, the leading coefficient of the divisor is $p_0=1$. Therefore, by rule 1, $f(x)$ is divisible by $x-a$ over the integers, the rational numbers, the real numbers and the complex numbers.

Repeated applications of the factor theorem results in more complicated divisors:
Rule 2 If a polynomial $f(x)$ satisfies:

$f(a)=f(b)=0,a\ne b$,

then $f(x)$ is divisible by $x^2-(a+b)x+ab$.
Proof By factor theorem, since $f(a)=0$, there exists a polynomial $q(x)$ such that:

$f(x)=(x-a)q(x)$.

Put $x=b$:

$f(b)=(b-a)q(b)$.

Since $f(b)=0$ and $a\ne b$, we conclude that $q(b)=0$. By factor theorem, there exists a polynomial $s(x)$ such that:

$q(x)=(x-b)s(x)$.

Therefore:

$f(x)=(x-a)(x-b)s(x)$,

$f(x)=(x^2-(a+b)x+ab)s(x)$.

Note that the leading coefficient of the divisor is 1.

Corollary 1 If a polynomial $f(x)$ with real coefficient satisfies $f(\alpha +\beta i)=0$, where $\alpha$ and $\beta$ are real numbers and $\beta \ne 0$, then $f(x)$ is divisible by $x^2-2\alpha x+({\alpha }^2+{\beta }^2)$.
Proof In algebra, we have already known that if a polynomial $f(x)$ with real coefficients vanishes at some complex number $z=\alpha +\beta i$, then it also vanishes at $\bar{z}=\alpha -\beta i$. So, we can apply rule 2 to obtain the required result, since $\beta \ne 0$ implies $\alpha +\beta i\ne \alpha -\beta i$.

The above corollary has a useful special case as shown below:
Corollary 2 If a polynomial $f(x)$ with integer coefficient satisfies $f(\omega )=0$, where $\omega =-\frac{1}{2}+\frac{\sqrt{3}}{2}i$ is a cube root of unity, then $f(x)$ is divisible by $x^2+x+1$.

Corollary 1 is an example of the application of the complex numbers in dealing with divisibility of polynomials with real coefficients. Corollary 2 further restricts to divisibility over the integers by the aid of the cube root of unity.

We can also apply other roots of unity in problems of polynomial divisibility, but we need some results similar to those shown above.

Rule 3 If a polynomial $f(x)$ satisfies:

$f(a_1)=f(a_2)=\cdots =f(a_n)=0$

for $n$ distinct numbers $a_1,a_2,\dots ,a_n$, then $f(x)$ is divisible by the product $(x-a_1)(x-a_2)\cdots (x-a_n)$.

Rule 4 is analogous to rule 3: they are repeated applications of the factor theorem.

Corollary 3 If a polynomial $f(x)$ with integer coefficient satisfies:

$f({ϵ}_k)=0$ where $k=\{\begin{array}{cc}1,2,\dots ,\frac{n}{2}& \text{if }n\text{ is even}\\ 1,2,\dots ,\frac{n-1}{2}& \text{if }n\text{ is odd},\end{array}$

then $f(x)$ is divisible by $x^{n-1}+x^{n-2}+\cdots +x^2+x+1$.

To prove this corollary, we have to use the result that conjugate of non-real roots of unity are also non-real roots of unity.

Using unit roots in problems of divisibility of polynomials

Example 2 Let $f(x)=x^{3m+1}+x^{3n+2}+1$, where $m$ and $n$ are integers. Prove that $f(x)$ is divisible by $x^2+x+1$.
Proof Put $x=\omega$, then:

$f(\omega )={\omega }^{3m+1}+{\omega }^{3n+2}+1=\omega +{\omega }^2+1=0$,

By corollary 2, $f(x)$ is divisible by $x^2+x+1$.

Example 3 Let $n$ be a natural number, and:

$f(x)=x^{n+2}+(x+1{)}^{2n+1}$.

Prove that for any integer $k$, $f(k)$ is a multiple of $k^2+k+1$.
Proof It is easy to show that $f(\omega )=0$ and $f(x)$ is a polynomial with integer coefficient. Therefore, $f(x)$ is divisible by $x^2+x+1$. As both $f(x)$ and $x^2+x+1$ are polynomials with integer coefficients, so is the quotient, say $q(x)$. Therefore, when $k$ is an integer, $f(k)$ is an integral multiple of $k^2+k+1$.

Example 4 Find the remainder from the division of $x^{1001}-1$ by $x^4+x^3+2x^2+x+1$.
Solution Write $f(x)=x^{1001}-1$ and $p(x)=x^4+x^3+2x^2+x+1$. Let the remainder be $r(x)$, then:

$f(x)=p(x)\cdot q(x)+r(x)$,

where $q(x)$ represents the quotient. Since the degree of the divisor $p(x)$ is 4, the degree of the remainder $r(x)$ is at most three. Therefore, we let:

$r(x)=a{x}^3+b{x}^2+cx+d$.

Now we are going to determine the coefficients of $r(x)$.
From:

$p(x)=(x^2+1)(x^2+x+1)$,

we know that:

$p(i)=p(\omega )=0$,

So:

$f(i)=r(i),f(\omega )=r(\omega )$

$i-1=-ai-b+ci+d,-\frac{3}{2}-\frac{\sqrt{3}}{2}i=a+d+\frac{b}{2}-\frac{c}{2}+(\frac{c\sqrt{3}}{2}-\frac{b\sqrt{3}}{2})i$

Compare the real parts and imaginary parts of both sides of these equations:

$d-b=-1,c-a=1,a+d-\frac{b}{2}-\frac{c}{2}=-\frac{3}{2},\frac{c\sqrt{3}}{2}-\frac{b\sqrt{3}}{2}=-\frac{\sqrt{3}}{2}$

Solving, $a=-1,b=1,c=d=0$. So, the remainder is $r(x)=-x^3+x^2$.

Example 5 Let $P(x)$, $Q(x)$, $R(x)$ and $S(x)$ be polynomials satisfying the identity:

$P(x^5)+xQ(x^5)+x^{2}R(x^5)=(x^4+x^3+x^2+x+1)S(x)$.

Prove that $x-1$ is a factor of $P(x)$.
Proof Let:

$P(x)=p_m{x}^m+p_{m-1}{x}^{m-1}+\cdots +p_1{x}^1+p_0$,

$S(x)=s_n{x}^n+s_{n-1}{x}^{n-1}+\cdots +s_1{x}^1+s_0$.

Note that $P(x^5)+xQ(x^5)+x^{2}R(x^5)$ only has $x^{5k}$-terms, $x^{5k+1}$-terms and $x^{5k+2}$-terms for non-negative integers $k$. Therefore, coefficients of $x^{5k-1}$-terms are all zero. Then:

$s_{5k-1}+s_{5k-2}+s_{5k-3}+s_{5k-4}+s_{5k-5}=0$.

On the other hand, by comparing the coefficients of $x^{5k}$-terms:

$p_0=s_0$,

$p_k=s_{5k}+s_{5k-1}+s_{5k-2}+s_{5k-3}+s_{5k-4}$

Therefore, $p_k=s_{5k}-s_{5k-5}$.
Now, we will prove $s_{5m}=0$. First, note that:

$0=p_{m+1}=p_{m+2}=\cdots =p_{m+h}$

So,

$0=p_{m+1}+p_{m+2}+\cdots +p_{m+h}$

$=(s_{5m+5}-s_{5m})+(s_{5m+10}-s_{5m+5})+\cdots +(s_{5m+5h}-s_{5m+5(h-1)})$

$=s_{5m+5h}-s_{5m}$ for any $h>0$.

In other words, $s_{5m}=s_{5m+5}=s_{5m+10}=\cdots$. Observe that $S(x)$ is a polynomial and therefore it has a finite degree. $s_{5m}\ne 0$ will result in a contradiction to this. Therefore, $s_{5m}=0$.
So:

$P(x)=s_0+(s_5-s_0)x+(s_{10}-s_5)x^2+\cdots +(s_{5m-5}-s_{5m-10})x^{m-1}+s_{5m-5}{x}^m$

$=-(x-1)(s_0+s_{5}x+s_{10}{x}^2+\cdots +s_{5m-5}{x}^{m-1})$. QED

Alternative proof Let ${ϵ}_k$ be a complex fifth root of unity, then:

$({ϵ}_k{)}^5=1$, $({ϵ}_k{)}^2={ϵ}_{2k}$, $({ϵ}_k{)}^4+({ϵ}_k{)}^3+({ϵ}_k{)}^2+{ϵ}_k+1=0$.

Put $x={ϵ}_k$ into the given identity:

$P(1)+{ϵ}_{k}Q(1)+{ϵ}_{2k}R(1)=0$.

We can obtain the following by first putting $k=1,2$ and then comparing the real parts and the imaginary parts respectively:

$P(1)+\frac{\sqrt{5}-1}{4}Q(1)-\frac{\sqrt{5}+1}{4}R(1)=0$,

$P(1)-\frac{\sqrt{5}+1}{4}Q(1)+\frac{\sqrt{5}-1}{4}R(1)=0$,

$\frac{\sqrt{10+2\sqrt{5}}}{4}Q(1)+\frac{\sqrt{10-2\sqrt{5}}}{4}R(1)=0$,

$\frac{\sqrt{10-2\sqrt{5}}}{4}Q(1)-\frac{\sqrt{10+2\sqrt{5}}}{4}R(1)=0$,

We can solve these equation easily:

$P(1)=Q(1)=R(1)=0$.

From factor theorem, $x-1$ is a factor of $P(x)$. QED

The alternative proof makes use of the properties of unit roots. By doing so, we can also conclude that $x-1$ is a factor of $Q(x)$ and $R(x)$, which implies that $S(x)$ also contains the factor $x-1$.

In the first proof, we only requires that the coefficients of $x^{5k-1}$-terms be zero. So, we can add one more term $x^{3}T(x^5)$ and the statement still holds:

Example 6 Let $P(x)$, $Q(x)$, $R(x)$, $T(x)$ and $S(x)$ be polynomials satisfying the identity:

$P(x^5)+xQ(x^5)+x^{2}R(x^5)+x^{3}T(x^5)=(x^4+x^3+x^2+x+1)S(x)$.

Prove that $x-1$ is a factor of $P(x)$.
Proof Repeat the first proof of the previous example.
Alternative proof Repeat the alternative proof of the previous example: putting $x={ϵ}_1,{ϵ}_2$ and comparing the real parts and imaginary parts. By this method, we can also conclude that all the polynomials $P(x)$, $Q(x)$, $R(x)$, $T(x)$ and $S(x)$ have the factor $x-1$.