Next: Quadratic Hensel Lifting
Up: Hensel Lifting
Previous: Hensel Lifting
Theorem 15
Let
R be a commutative ring with identity element.
Let
f,
g_{0},
h_{0} be univariate polynomials in
R[
x]
and let
m R.
We assume that the following relation holds
f g_{0} h_{0} modm 
(121) 
We assume also that
g_{0} and
h_{0} are relatively prime modulo
m,
that is there exists
s,
t R such that
sg_{0} + th_{0} 1 modm 
(122) 
Then, for every integer
there exist
g^{()},
h^{()} R[
x] such that we have

f g^{()}h^{()}modm^{},

g_{0} g^{()}modm.
Proof.
We apply Theorem
13 with
= m, n = 1, r = 2, f_{1}(x_{1}, x_{2}) = x_{1}x_{2}  f. 
(123) 
Thus we have
U = u_{11} u_{12} = g_{0} h_{0} 
(124) 
Observe that this matrix is leftinvertible modulo
m if and only if
g_{0},
h_{0}
are relatively prime modulo
m.
Indeed, the matrix
U is leftinvertible modulo
m iff there exists
a matrix
such that
U U^{1} 1
mod
m, that is
sg_{0} + th_{0} 1 modm 
(125) 
We prove now the claim of the theorem.
Assume we have computed
g^{()},
h^{()} R
such that
f g^{()}h^{()}mod
m^{}
and
g g^{()}mod
m hold.
We want to compute
g^{(+1)},
h^{(+1)} R.
Let
v be such that
f_{1}(g^{()}, h^{()}) = g^{()}h^{()}  f = vm^{} 
(126) 
We look for
g_{},
h_{} R such that
g^{(+1)} = g^{()} + g_{}m^{} and h^{(+1)} = h^{()} + h_{}m^{} 
(127) 
Following the proof of Theorem
13 we are led to solve the equation
v + g_{}h_{0} + h_{}g_{0} 0 modm 
(128) 
A solution of this equation is
This proves the claim of the theorem.
Remark 23
The proof of Theorem 15 provides
a solution
(g_{}, h_{}) to
Equation (128).
It is desirable to add constraints such that
Equation (128)
has a unique soulution.
In particular, one would like to guarantee that for every integer
the polynomials
g^{()} and g_{0} have the same degree.
This problem is solved in the following subsection
where we study Linear Diophantine Equations.
Definition 10
Let
R be a commutative ring with identity element.
A
linear Diophantine equation over
R is an equation
of the form
f_{1}s_{1} + ^{ ... } + f_{n}s_{n} = a 
(130) 
where
f_{1},...,
f_{n},
a are given in
R
and where
s_{1},...,
s_{n} are unknowns in
R.
Theorem 16
Let
R be an Euclidean domain and let
f,
g,
h,
a R
such that
h = gcd(
f,
g).
We consider the linear Diophantine equation
Then the following hold
 (i)
 Equation (131) has a solution
if and only if h divides a.
 (ii)
 If h 0 and if
(s_{0}, t_{0}) R^{2} is a solution of
Equation (131)
then every other solution is of the form
(s_{0} + r, t_{0}  r) where r R. 
(132) 
 (iii)
 If R = F[x] where F is a field, h 0, and if
Equation (131)
is solvable, where
degf + degg  degh > dega 
(133) 
then there is a unique solution
(s_{0}, t_{0}) R^{2} of
Equation (131)
such that
degs < degg  degh and degt < degf  degh. 
(134) 
Proof.
First we prove (
i).
If
(
s_{0},
t_{0})
R^{2} is a solution of Equation (
131),
then
h which divides
s_{0}f +
t_{0}g, divides also
a.
Conversly, we assume that
h = gcd(
f,
g) divides
a.
The claim is trivial if
h = 0. (Indeed, this implies
f =
g = 0 and also
a = 0.)
Otherwise, let
(
s_{0},
t_{0})
R^{2} be computed by the Extended Euclidean Algorithm
applied to (
f,
g), such that we have
s_{0}f +
t_{0}g =
h.
Then
(
s,
t) = (
s_{0}a/
h,
t_{0}a/
h) is a solution of
Equation (
131).
Now we prove (ii). Assume h 0 and let
(s_{0}, t_{0}) R^{2} is a solution of
Equation (131).
Since h 0, then f /h and g/h are coprime.
Let (s, t) be in R^{2}.
Then we have
sf + tg = a 

(s  s_{0})f + (t  t_{0})g = 0 


(s  s_{0})(f /h) =  (t  t_{0})(g/h) 


(s  s_{0})(f /h) = (t_{0}  t)(g/h) 


(g/h)  (s  s_{0}) and (f /h)  (t_{0}  t) 


(r R) (s  s_{0}) = r(g/h) and (t_{0}  t) = r(f /h) 


(r R) s = s_{0} + r(g/h) and t = t_{0}  r(f /h). 


Finally, we prove (
iii). Let
(
s_{1},
t_{1})
R^{2} be a solution of
Equation (
131).
Let
q and
t_{0} be the quotient and the remainder of
t_{1} w.r.t.
f /
h.
Hence we have
t_{1} = f /hq + t_{0} and degt_{0} < degf  degh. 
(135) 
We define
s_{0} = s_{1} + qg/h. 
(136) 
Observe that
(s_{0}, t_{0}) = (s_{1}, t_{1}) + q(g/h,  f /h) 

solves Equation (
131) too.
By Relation (
135) and by hypothesis we have
deg(t_{0}g) < degf + degg  degh and dega < degf + degg  degh 

leading to
degs_{0} + degf = degs_{0}f = deg(a  t_{0}g) < degf + degg  degh. 

Therefore we have
degt_{0} < degf  degh and degs_{0} < degg  degh. 

This proves the existence. Let us prove the unicity.
Let (
s,
t) be a solution of Equation (
131).
We know that there exists
r R such that
s =
s_{0} +
rg/
h.
Since
deg
s_{0} < deg
g  deg
h holds, if
r 0, we have
degs deg(g/h) = degg  degh. 

This implies the uniquemess.
Theorem 17
Let
R be a commutative ring with identity element.
Let
f,
g_{0},
h_{0} be univariate
monic polynomials in
R[
x].
Let
m R be such that
R/
m is a field.
We assume that the following relation holds
f g_{0} h_{0} modm 
(137) 
and that
g_{0} and
h_{0} are relatively prime modulo
m.
Then, for every integer
there exist
unique monic polynomials
g^{()},
h^{()} R[
x] such that we have

f g^{()}h^{()}modm^{},

g_{0} g^{()}modm,

h_{0} h^{()}modm.
Proof.
By induction on
1.
The clain is clear for
= 1.
So let us assume it is true for
1
and consider monic polynomials
g^{(+1)},
h^{(+1)} R[
x]
satisfying
f g^{(+1)}h^{(+1)}modm^{+1} 
(138) 
and
g_{0} g^{(+1)}modm and h_{0} h^{(+1)}modm. 
(139) 
Such polynomials
g^{(+1)},
h^{(+1)} exist
by Theorem
15.
(The fact that they can be chosen monic is left to the reader
as an exercise.)
Observe that we have
f g^{(+1)}h^{(+1)}modm^{} 
(140) 
So the induction hypothesis leads to
g^{()} g^{(+1)}modm^{} and h^{()} h^{(+1)}modm^{} 
(141) 
Hence there exist polynomials
q_{g},
q_{h} (
R/
m)[
x] such that
g^{(+1)} = g^{()} + m^{}q_{g} and h^{(+1)} = h^{()} + m^{}q_{h}. 
(142) 
Since
f,
g_{0},
h_{0} are given to be monic, it is easy to prove
that for
k 1 we have
degq_{g} < degg_{0} and degq_{h} < degh_{0} 
(143) 
In addition, observe that combining
Equation (
138)
and
Equation (
142)
we obtain
f 

g^{()}h^{()} + g^{()}q_{h} + h^{()}q_{g}m^{}modm^{+1} 

(144) 
The induction hypothesis shows that
f 
g^{()}h^{()} is a multiple of
m^{}.
Then we obtain
g_{0}q_{h} + h_{0}q_{g} modm. 
(145) 
By Theorem
16
and
Equation (
143),
the Equation (
145)
has a unique solution.
Next: Quadratic Hensel Lifting
Up: Hensel Lifting
Previous: Hensel Lifting
Marc Moreno Maza
20040427