TAOCP 4.6.2 Exercise 22
Assume that for some $r \ge 1$ we are given polynomials u(x),\ v_s(x),\ w_s(x),\ \alpha(x),\ \beta(x)\in\mathbb Z[x] such that
Section 4.6.2: Factorization of Polynomials
Exercise 22. ▶ [M24] (Hensel's Lemma.) Let $u(x)$, $v_0(x)$, $w_0(x)$, $\alpha(x)$, $b(x)$ be polynomials with integer coefficients, satisfying the relations
$$u(x) \equiv v_0(x) w_0(x) \pmod{p^r}, \quad \alpha(x) v_0(x) + b(x) w_0(x) \equiv 1 \pmod{p},$$
where $p$ is prime, $p \ge 1$, $v_0(x)$ is monic, $\deg(u) < \deg(v_0) + \deg(w_0)$, $\deg(b) < \deg(v_0)$, and $\deg(u) = \deg(v_0) + \deg(w_0)$ (modulo $p^r$). Show how to compute polynomials $v_{s+1}(x) \equiv v_s(x)$ and $w_{s+1}(x) \equiv w_s(x)$ (modulo $p^r$), satisfying the same conditions with $r$ increased by 1. Furthermore, prove that $v_{s+1}(x)$ and $w_{s+1}(x)$ are unique, modulo $p^{r+1}$.
Use your method to prove that if $u(x)$ is irreducible over the integers, then $u(x)$ is irreducible modulo 2 found in exercise 10. (Note that Euclid's extended algorithm, exercise 4.6.1–3, will get the process started for $r = 1$.)
Verified: yes
Solve time: 4m46s
Solution
Assume that for some $r \ge 1$ we are given polynomials
$$ u(x),\ v_s(x),\ w_s(x),\ \alpha(x),\ \beta(x)\in\mathbb Z[x] $$
such that
$$ u(x)\equiv v_s(x)w_s(x)\pmod{p^r}, $$
$$ \alpha(x)v_s(x)+\beta(x)w_s(x)\equiv1\pmod p, $$
where $v_s(x)$ is monic,
$$ \deg u=\deg v_s+\deg w_s, $$
and
$$ \deg \beta<\deg v_s. $$
Since $v_s\equiv v_0\pmod p$ and $w_s\equiv w_0\pmod p$, the Bézout relation modulo $p$ persists at every stage.
We shall construct polynomials $v_{s+1},w_{s+1}$ satisfying
$$ v_{s+1}\equiv v_s\pmod{p^r},\qquad w_{s+1}\equiv w_s\pmod{p^r}, $$
and
$$ u\equiv v_{s+1}w_{s+1}\pmod{p^{r+1}}. $$
We shall also prove uniqueness modulo $p^{r+1}$.
Step 1. Setting up the correction equation
Since
$$ u-v_sw_s\equiv0\pmod{p^r}, $$
there exists $z(x)\in\mathbb Z[x]$ such that
$$ u-v_sw_s=p^rz. $$
Seek corrections of the form
$$ v_{s+1}=v_s+p^ra, \qquad w_{s+1}=w_s+p^rb, $$
where $a,b\in\mathbb Z[x]$ are to be determined.
Expanding,
$$ v_{s+1}w_{s+1} = v_sw_s+p^r(aw_s+bv_s)+p^{2r}ab. $$
Since $2r\ge r+1$,
$$ p^{2r}ab\equiv0\pmod{p^{r+1}}, $$
hence
$$ v_{s+1}w_{s+1} \equiv v_sw_s+p^r(aw_s+bv_s) \pmod{p^{r+1}}. $$
Therefore the condition
$$ u\equiv v_{s+1}w_{s+1}\pmod{p^{r+1}} $$
is equivalent to
$$ aw_s+bv_s\equiv z\pmod p. \tag{1} $$
Reducing modulo $p$, we may replace $v_s,w_s$ by $v_0,w_0$. Thus we require
$$ aw_0+bv_0\equiv z\pmod p. \tag{2} $$
Step 2. Construction of the correction polynomials
From
$$ \alpha v_0+\beta w_0\equiv1\pmod p, $$
multiply by $z$:
$$ z\alpha v_0+z\beta w_0\equiv z\pmod p. $$
Hence any pair satisfying
$$ a\equiv z\beta\pmod p, \qquad b\equiv z\alpha\pmod p $$
will satisfy (2).
However, we must impose degree conditions. Since $v_0$ is monic, divide $z\beta$ by $v_0$:
$$ z\beta=qv_0+r, \qquad \deg r<\deg v_0. $$
Define
$$ a=r, \qquad b=z\alpha+qw_0. $$
Then modulo $p$,
$$ aw_0+bv_0 = rw_0+(z\alpha+qw_0)v_0 = (z\beta-qv_0)w_0+z\alpha v_0+qw_0v_0. $$
The terms involving $q$ cancel, giving
$$ aw_0+bv_0 = z(\alpha v_0+\beta w_0) \equiv z\pmod p. $$
Thus (2) holds.
Moreover,
$$ \deg a<\deg v_0. $$
Therefore
$$ v_{s+1}=v_s+p^ra $$
has the same degree as $v_s$, and since $a$ has smaller degree than $v_s$, the leading coefficient of $v_{s+1}$ remains $1$. Hence $v_{s+1}$ is monic.
Similarly,
$$ \deg w_{s+1}=\deg w_s, $$
because the correction term has lower degree.
Thus the degree conditions are preserved.
This completes the lifting step.
Uniqueness modulo $p^{r+1}$
Suppose that
$$ (v',w') \quad\text{and}\quad (v'',w'') $$
are two lifts satisfying
$$ v'\equiv v''\equiv v_s\pmod{p^r}, \qquad w'\equiv w''\equiv w_s\pmod{p^r}, $$
and
$$ u\equiv v'w'\equiv v''w''\pmod{p^{r+1}}. $$
Write
$$ v''=v'+p^r\delta v, \qquad w''=w'+p^r\delta w. $$
Since both pairs have the same degrees as $v_s,w_s$,
$$ \deg\delta v<\deg v_0, \qquad \deg\delta w<\deg w_0. $$
Now
$$ v''w''-v'w' = p^r(\delta v,w'+\delta w,v') +p^{2r}\delta v,\delta w. $$
Because both products are congruent to $u$ modulo $p^{r+1}$,
$$ p^r(\delta v,w'+\delta w,v') \equiv0\pmod{p^{r+1}}. $$
Dividing by $p^r$,
$$ \delta v,w'+\delta w,v'\equiv0\pmod p. $$
Reducing modulo $p$,
$$ \delta v,w_0+\delta w,v_0\equiv0\pmod p. \tag{3} $$
Multiply (3) by $\alpha$:
$$ \alpha\delta v,w_0+\alpha\delta w,v_0\equiv0\pmod p. $$
Using
$$ \alpha v_0\equiv1-\beta w_0\pmod p, $$
we obtain
$$ \alpha\delta v,w_0+\delta w-\beta\delta w,w_0 \equiv0\pmod p, $$
hence
$$ \delta w \equiv (\beta\delta w-\alpha\delta v)w_0 \pmod p. $$
Thus $w_0$ divides $\delta w$ modulo $p$. But
$$ \deg\delta w<\deg w_0, $$
therefore
$$ \delta w\equiv0\pmod p. $$
Substituting into (3),
$$ \delta v,w_0\equiv0\pmod p. $$
Since $w_0$ is relatively prime to $v_0$ modulo $p$, it is not a zero divisor in the quotient ring modulo $v_0$. Because
$$ \deg\delta v<\deg v_0, $$
it follows that
$$ \delta v\equiv0\pmod p. $$
Consequently,
$$ v''\equiv v'\pmod{p^{r+1}}, \qquad w''\equiv w'\pmod{p^{r+1}}. $$
Hence the lift is unique modulo $p^{r+1}$.
Application to irreducibility modulo $2$
Suppose $u(x)\in\mathbb Z[x]$ is monic and reducible modulo $2$:
$$ u(x)\equiv v_0(x)w_0(x)\pmod2, $$
where $v_0,w_0$ are nonconstant and relatively prime modulo $2$.
By Euclid's algorithm over $(\mathbb Z/2\mathbb Z)[x]$, there exist $\alpha,\beta$ such that
$$ \alpha v_0+\beta w_0\equiv1\pmod2. $$
Applying the lifting procedure repeatedly, we obtain for every $r\ge1$ polynomials $v_r,w_r\in\mathbb Z[x]$ satisfying
$$ u\equiv v_rw_r\pmod{2^r}, $$
with fixed degrees
$$ \deg v_r=\deg v_0, \qquad \deg w_r=\deg w_0. $$
The uniqueness modulo $2^r$ implies compatibility:
$$ v_{r+1}\equiv v_r\pmod{2^r}, \qquad w_{r+1}\equiv w_r\pmod{2^r}. $$
Hence the coefficients stabilize $2$-adically. Therefore there exist formal $2$-adic power series $v,w\in\mathbb Z_2[x]$ such that
$$ u=vw $$
in $\mathbb Z_2[x]$.
But $u$ has integer coefficients and fixed degree, so the coefficients of $v_r,w_r$ are bounded ordinary integers. A bounded sequence converging $2$-adically is eventually constant, hence for sufficiently large $r$ the coefficients stabilize as ordinary integers. Therefore $u$ factors in $\mathbb Z[x]$:
$$ u=v^\ast w^\ast, $$
with nonconstant integer polynomials $v^\ast,w^\ast$.
Thus any nontrivial factorization modulo $2$ lifts to a nontrivial factorization over $\mathbb Z$.
Consequently, if $u(x)$ is irreducible over $\mathbb Z$, then $u(x)$ must be irreducible modulo $2$.