TAOCP 4.6.2 Exercise 3

Let U(x)=u_1(x)u_2(x)\cdots u_r(x), where the polynomials $u_1,\ldots,u_r$ are pairwise relatively prime over the field $S$.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.2: Factorization of Polynomials

Exercise 3. [M25] (The Chinese remainder theorem for polynomials.) Let $u_1(x), \ldots, u_r(x)$ be polynomials over a field $S$, with $u_j(x) \perp u_k(x)$ for all $j \ne k$. For any given polynomials $w_1(x), \ldots, w_r(x)$ over $S$, prove that there is a unique polynomial $v(x)$ over $S$ such that $\deg(v) < \deg(u_1) + \cdots + \deg(u_r)$ and $v(x) \equiv w_j(x) \pmod{u_j(x)}$ for $1 \le j \le r$. Does this result hold also when $S$ is the set of all integers?

Verified: yes
Solve time: 4m18s

Solution

Let

$$ U(x)=u_1(x)u_2(x)\cdots u_r(x), $$

where the polynomials $u_1,\ldots,u_r$ are pairwise relatively prime over the field $S$.

For each $j$, define

$$ U_j(x)=\frac{U(x)}{u_j(x)}. $$

Since $u_j(x)\perp U_j(x)$ and $S[x]$ is a Euclidean domain, there exist polynomials $a_j(x)$ and $b_j(x)$ such that

$$ a_j(x)U_j(x)+b_j(x)u_j(x)=1. $$

Hence

$$ a_j(x)U_j(x)\equiv 1 \pmod{u_j(x)}, $$

and for $k\ne j$,

$$ a_k(x)U_k(x)\equiv 0 \pmod{u_j(x)}, $$

because $u_j(x)$ divides $U_k(x)$.

Consider

$$ V(x)=\sum_{j=1}^r w_j(x)a_j(x)U_j(x). $$

Modulo $u_j(x)$ all terms vanish except the $j$th one, therefore

$$ V(x)\equiv w_j(x)\pmod{u_j(x)} \qquad (1\le j\le r). $$

Let $v(x)$ be the remainder when $V(x)$ is divided by $U(x)$. Then

$$ \deg(v)<\deg(U) =\deg(u_1)+\cdots+\deg(u_r), $$

and

$$ v(x)\equiv V(x)\equiv w_j(x)\pmod{u_j(x)} \qquad (1\le j\le r). $$

Thus a polynomial satisfying the required congruences exists.

To prove uniqueness, suppose that $v(x)$ and $\tilde v(x)$ both satisfy the conditions. Then

$$ v(x)-\tilde v(x)\equiv 0 \pmod{u_j(x)} \qquad (1\le j\le r). $$

Hence every $u_j(x)$ divides $v(x)-\tilde v(x)$. Since the $u_j$ are pairwise relatively prime, their product $U(x)$ divides $v(x)-\tilde v(x)$. But

$$ \deg!\bigl(v-\tilde v\bigr)<\deg(U), $$

so the only multiple of $U$ of such degree is the zero polynomial. Therefore

$$ v(x)=\tilde v(x). $$

This proves existence and uniqueness.

For the final question, the result does not hold when $S$ is the set of all integers.

Take

$$ u_1(x)=x,\qquad u_2(x)=x+2, $$

which satisfy $u_1\perp u_2$ in the sense that they have no nonconstant common divisor in $\mathbf Z[x]$. Let

$$ w_1(x)=0,\qquad w_2(x)=1. $$

If a polynomial $v(x)\in\mathbf Z[x]$ satisfied

$$ v(x)\equiv 0\pmod{x}, \qquad v(x)\equiv 1\pmod{x+2}, $$

then $x\mid v(x)$, so $v(0)=0$.

Also,

$$ v(x)-1=(x+2)q(x) $$

for some $q(x)\in\mathbf Z[x]$. Setting $x=0$ gives

$$ v(0)-1=2q(0), $$

hence $v(0)\equiv 1\pmod 2$.

This contradicts $v(0)=0$. Therefore no such polynomial exists.

Consequently, the Chinese remainder theorem stated above is valid over a field, but it does not extend in general to the ring of integers.

This completes the proof.

∎