Proof.
Since
^{}(
g) is invertible modulo
p
then
^{}(
g) is invertible modulo
p^{2}.
(This is easy to check: Exercise!)
Hence Relation
111 makes sense.
In fact, Algorithm
6
computes
^{}(
g)
^{1}mod
p^{2}
given
^{}(
g)
^{1}mod
p.
Since p divides p^{2}, the following congruence holds
h g  (g) ^{}(g)^{1}modp 
(112) 
Since
(
g)
0 mod
p, this leads to
h g modp 
(113) 
and we have proved the second claim.
Let us prove the first one.
Using the Taylor expansion of
at
h
and the fact that
p^{2} divides (
h 
g)
^{2} we obtain
(h) 

(g) + ^{}(g)(h  g)modp^{2} 


(g)  ^{}(g)(g) ^{}(g)^{1}modp^{2} 


0 modp^{2} 

(114) 
proving the first claim.
Finally, observe that
h g mod
p implies
^{}(
h)
^{}(
g)mod
p.
Indeed
^{} is a polynomial in
R[
x].
Therefore,
^{}(
h) is invertible modulo
p,
since
^{}(
g) is invertible modulo
p, by hypothesis.
Proof.
Let
g_{r} g_{r1} 
(
g_{r1})
s_{r1}mod
p^{2r}.
Then we have
g g_{r} modp^{} 
(116) 
In other words
g_{r} is a
solution of higher precision.
Then proving the theorem turns into proving the invariants for
i = 0
^{ ... }r

g_{i} g_{0}modp,

(g_{i}) 0 modp^{2i},
 if i < r then
s_{i} ^{}(g_{i}) 1 modp^{2i}.
The case
i = 0 is clear and we assume that
i > 0 holds.
Then by induction hypothesis
p^{2i1} divides
(
g_{i1}) and
s_{i1} 
^{}(
g_{i1})
^{1}.
Then
p^{2i} divides their product, that is
(g_{i1})s_{i1} (g_{i1})^{}(g_{i1})^{1} modp^{2i}. 
(117) 
Now we calculate
g_{i} 

g_{i1}  (g_{i1})s_{i1} modp^{2i} 


g_{i1}  (g_{i1})^{}(g_{i1})^{1} modp^{2i} 

(118) 
Now applying Proposition
15
with
g =
g_{i1},
h =
g_{i} and
m =
p^{2i1}
we obtain the first two invariants.
In addition, this leads to
g_{i} g_{i1} modp^{2i1} 
(119) 
for
i <
r.
This implies
^{}(g_{i})^{1} ^{}(g_{i1})^{1} s_{i1} modp^{2i1} 
(120) 
Now,
s_{i} is obtained by one Newton step for inversion
(see Algorithm
6).
Therefore the third invariant follows.