Proof.
We apply Theorem
![[*]](crossref.png)
with
![$\displaystyle {\cal I} = \langle m \rangle, \ n = 1, \ r = 2, \ f_1(x_1, x_2) = x_1 x_2 - f.$](img62.png) |
(10) |
Thus we have
![$\displaystyle U \ = \ \left( u_{11} \ u_{12} \right) \ = \ \left(g_0 \ h_0 \right)$](img63.png) |
(11) |
Observe that this matrix is left-invertible modulo
![$ m$](img55.png)
if and only if
![$ g_0, h_0$](img64.png)
are relatively prime modulo
![$ m$](img55.png)
.
Indeed, the matrix
![$ U$](img65.png)
is left-invertible modulo
![$ m$](img55.png)
iff there exists
a matrix
such that
![$ U \, U^{-1} \ \equiv \ \left( 1 \right) \mod{ m}$](img67.png)
, that is
![$\displaystyle s g_0 + t h_0 \ \equiv \ 1 \ \mod{ m}$](img57.png) |
(12) |
We prove now the claim of the theorem.
Assume we have computed
![$ g^{({\ell})}, h^{({\ell})} \in R$](img68.png)
such that
![$ f \ \equiv \ g^{({\ell})} h^{({\ell})} \mod{m^{\ell}}$](img60.png)
and
![$ g \ \equiv \ g^{({\ell})} \mod{ m}$](img69.png)
hold.
We want to compute
![$ g^{({\ell}+1)}, h^{({\ell}+1)} \in R$](img70.png)
.
Let
![$ v$](img71.png)
be such that
![$\displaystyle f_1(g^{({\ell})}, h^{({\ell})}) = g^{({\ell})} h^{({\ell})} -f = v m^{\ell}$](img72.png) |
(13) |
We look for
![$ g_{\ell}, h_{\ell} \in R$](img73.png)
such that
![$\displaystyle g^{({\ell}+1)} = g^{({\ell})} + g_{\ell} m^{{\ell}} \ \ {\rm and} \ \ h^{({\ell}+1)} = h^{({\ell})} + h_{\ell} m^{{\ell}}$](img74.png) |
(14) |
Following the proof of Theorem
![[*]](crossref.png)
we are led to solve the equation
![$\displaystyle v + g_{\ell} h_0 + h_{\ell} g_0 \equiv \ 0 \ \mod{ m}$](img75.png) |
(15) |
A solution of this equation is
![$\displaystyle \left(\begin{array}{c} g_{\ell} \\ h_{\ell} \end{array} \right) = \left( \begin{array}{c} - s v\\ - t v \end{array} \right)$](img76.png) |
(16) |
This proves the claim of the theorem.
Proof.
By induction on
![$ {\ell} \geq 1$](img81.png)
.
The clain is clear for
![$ {\ell} = 1$](img82.png)
.
So let us assume it is true for
![$ {\ell} \geq 1$](img81.png)
and consider monic polynomials
![$ g^{({\ell}+1)}, h^{({\ell}+1)} \in R[x]$](img83.png)
satisfying
![$\displaystyle f \ \equiv \ g^{({\ell}+1)} h^{({\ell}+1)} \mod{m^{{\ell}+1}}$](img84.png) |
(18) |
and
![$\displaystyle g_0 \ \equiv \ g^{({\ell}+1)} \mod{ m} \ \ {\rm and} \ \ h_0 \ \equiv \ h^{({\ell}+1)} \mod{ m}.$](img85.png) |
(19) |
Such polynomials
![$ g^{({\ell}+1)}, h^{({\ell}+1)}$](img86.png)
exist
by Theorem
3.
(The fact that they can be chosen monic is left to the reader
as an exercise.)
Observe that we have
![$\displaystyle f \ \equiv \ g^{({\ell}+1)} h^{({\ell}+1)} \mod{m^{{\ell}}}$](img87.png) |
(20) |
So the induction hypothesis leads to
![$\displaystyle g^{({\ell})} \ \equiv \ g^{({\ell}+1)} \mod{m^{\ell}} \ \ {\rm and} \ \ h^{({\ell})} \ \equiv \ h^{({\ell}+1)} \mod{m^{\ell}}$](img88.png) |
(21) |
Hence there exist polynomials
![$ q_g, q_h \in (R/m)[x]$](img89.png)
such that
![$\displaystyle g^{({\ell}+1)} = g^{({\ell})} + m^{\ell} q_g \ \ {\rm and} \ \ h^{({\ell}+1)} = h^{({\ell})} + m^{\ell} q_h.$](img90.png) |
(22) |
Since
![$ f,g_0,h_0$](img49.png)
are given to be monic, it is easy to prove
that for
![$ k \geq 1$](img91.png)
we have
![$\displaystyle {\deg} q_g < {\deg} g_0 \ \ {\rm and} \ \ {\deg} q_h < {\deg} h_0$](img92.png) |
(23) |
In addition, observe that combining
Equation (
18)
and
Equation (
22)
we obtain
![\begin{displaymath}\begin{array}{rcl} f & \equiv & g^{({\ell})} h^{({\ell})} + \...
...{\ell})} q_g \right) m^{\ell} \mod{m^{{\ell}+1}} \\ \end{array}\end{displaymath}](img93.png) |
(24) |
The induction hypothesis shows that
![$ f - g^{({\ell})} h^{({\ell})}$](img94.png)
is a multiple of
![$ m^{\ell}$](img95.png)
.
Then we obtain
![$\displaystyle g_0 q_h + h_0 q_g \ \equiv \ \frac{f - g^{({\ell})} h^{({\ell})} }{m^{\ell}} \mod{ m}.$](img96.png) |
(25) |
By Theorem
1
and
Equation (
23),
the Equation (
25)
has a unique solution.