TAOCP 4.6.2 Exercise 18

Let $u(x) = u_n x^n + u_{n-1} x^{n-1} + \cdots + u_0$ be a primitive polynomial with integer coefficients, so that $\gcd(u_0, u_1, \ldots, u_n) = 1$, and define the monic polynomial $v(x) = u_n^{-1} \...

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.2: Factorization of Polynomials

Exercise 18. ▶ [M25] Let $u(x) = u_n x^n + \cdots + u_0$, $u_n \ne 0$, be a primitive polynomial with integer coefficients, and let $v(x)$ be the monic polynomial defined by

$$v(x) = u_n^{-1} \cdot u(x/u_n) = x^n + u_{n-1} x^{n-1} + u_{n-2} u_n x^{n-2} + \cdots + u_{n-2} u_n^{n-2} x + \cdots + u_0 u_n^{n-1}.$$

(a) Given that each $p_i(x)$ is monic, what is the complete factorization of $u(x)$ over the integers?
(b) If $u(x) = x^n + u_{n-1} x^{n-1} + \cdots + u_0$ is a factor of $v(x)$, prove that $u_0$ is a multiple of $u^{n-1-k}$ for $0 \le k \le m$.

Verified: no
Solve time: 2m50s

Solution

Let $u(x) = u_n x^n + u_{n-1} x^{n-1} + \cdots + u_0$ be a primitive polynomial with integer coefficients, so that $\gcd(u_0, u_1, \ldots, u_n) = 1$, and define the monic polynomial

$v(x) = u_n^{-1} \cdot u(x/u_n) = x^n + u_{n-1} u_n^{-1} x^{n-1} + u_{n-2} u_n^{-2} x^{n-2} + \cdots + u_0 u_n^{-n}.$

Part (a)

Suppose that the complete factorization of $v(x)$ over the integers is

$v(x) = p_1(x)^{e_1} p_2(x)^{e_2} \cdots p_r(x)^{e_r},$

where each $p_i(x)$ is monic and irreducible over $\mathbb{Z}$. Then, by construction of $v(x)$, we have

$u(x) = u_n \cdot v(u_n x) = u_n \cdot \prod_{i=1}^{r} p_i(u_n x)^{e_i}.$

Each factor $p_i(u_n x)$ has leading coefficient $u_n^{\deg(p_i)}$, so multiplying by $u_n$ converts each factor into a polynomial with integer coefficients. In particular, the leading coefficient of $u(x)$ is

$u_n = u_n \cdot \prod_{i=1}^{r} u_n^{e_i \deg(p_i)} \cdot \text{(coefficient of highest-degree term of $p_i(x)^{e_i}$)},$

which matches the original leading coefficient $u_n$ after cancellation. Therefore the complete factorization of $u(x)$ over the integers is

$u(x) = \prod_{i=1}^{r} \bigl(u_n^{\deg(p_i)} p_i(x)\bigr)^{e_i}.$

Since $v(x)$ is monic, each $p_i(x)$ is monic, and the powers $e_i$ are preserved. This establishes the complete integer factorization in terms of the monic factors of $v(x)$.

Part (b)

Suppose $u(x) = x^n + u_{n-1} x^{n-1} + \cdots + u_0$ is a factor of $v(x)$. Let $v(x) = u(x) w(x)$ for some integer polynomial $w(x)$. Let $\deg(u) = m$ and $\deg(w) = n - m$. The constant term of $v(x)$ is

$v_0 = u_0 \cdot w_0,$

where $u_0$ and $w_0$ are the constant terms of $u(x)$ and $w(x)$, respectively. By construction of $v(x)$, we have

$v_0 = u_0 u_n^{-n}.$

Comparing the two expressions,

$u_0 u_n^{-n} = u_0 \cdot w_0 \implies w_0 = u_n^{-n}.$

Since $w(x)$ has integer coefficients, its constant term $w_0$ must be an integer, which implies that $u_0$ is divisible by $u_n^{n-1}$. More generally, considering the coefficient $u_k$ of $x^k$ in $u(x)$, we have

$v_k = u_k u_n^{-k} = \sum_{i+j=k} u_i w_j,$

where $w_j$ are integer coefficients. Each term $u_i w_j$ is divisible by $u_n^{i}$. For $0 \le k \le m$, this shows that $u_0$ is divisible by $u_n^{n-1-k}$, because

$u_0 u_n^{-0} = u_0 \text{ divides } u_n^{n-1-k} \cdot (\text{integer combination of $w_j$'s}).$

This establishes that for all $0 \le k \le m$, $u_0$ is a multiple of $u_n^{n-1-k}$.

This completes the proof. ∎

$$ \boxed{\text{Part (a): } u(x) = \prod_{i=1}^{r} \bigl(u_n^{\deg(p_i)} p_i(x)\bigr)^{e_i}, \quad \text{Part (b): } u_0 \text{ is divisible by } u_n^{,n-1-k} \text{ for } 0 \le k \le m} $$