# Linear Hensel Lifting

Theorem 3   Let be a commutative ring with identity element. Let be univariate polynomials in and let . We assume that the following relation holds

 (8)

We assume also that and are relatively prime modulo , that is there exists such that

 (9)

Then, for every integer there exist such that we have
1. ,
2. .

Proof. We apply Theorem  with

 (10)

Thus we have

 (11)

Observe that this matrix is left-invertible modulo if and only if are relatively prime modulo . Indeed, the matrix is left-invertible modulo iff there exists a matrix

such that , that is

 (12)

We prove now the claim of the theorem. Assume we have computed such that and hold. We want to compute . Let be such that

 (13)

We look for such that

 (14)

Following the proof of Theorem  we are led to solve the equation

 (15)

A solution of this equation is

 (16)

This proves the claim of the theorem.

Remark 1   The proof of Theorem 3 provides a solution to Equation (15). It is desirable to add constraints such that Equation (15) has a unique soulution. In particular, one would like to guarantee that for every integer the polynomials and have the same degree. As we shall see now, this problem was solved, in fact, by our preliminary study of Linear Diophantine Equations.

Theorem 4   Let be a commutative ring with identity element. Let be univariate monic polynomials in . Let be such that is a field. We assume that the following relation holds

 (17)

and that and are relatively prime modulo . Then, for every integer there exist unique monic polynomials such that we have
1. ,
2. ,
3. .

Proof. By induction on . The clain is clear for . So let us assume it is true for and consider monic polynomials satisfying

 (18)

and

 (19)

Such polynomials exist by Theorem 3. (The fact that they can be chosen monic is left to the reader as an exercise.) Observe that we have

 (20)

So the induction hypothesis leads to

 (21)

Hence there exist polynomials such that

 (22)

Since are given to be monic, it is easy to prove that for we have

 (23)

In addition, observe that combining Equation (18) and Equation (22) we obtain

 (24)

The induction hypothesis shows that is a multiple of . Then we obtain

 (25)

By Theorem 1 and Equation (23), the Equation (25) has a unique solution.

Marc Moreno Maza
2008-01-07