**Let
be a commutative ring with units.
Let
and
.
We are concerned with solving the equation
**

(30) |

- ,
- ,
- is invertible modulo , and thus modulo .

Since divides , the following congruence holds

(32) |

Since , this leads to

(33) |

and we have proved the second claim. Let us prove the first one. Using the Taylor expansion of at and the fact that divides we obtain

(34) |

proving the first claim. Finally, observe that implies . Indeed is a polynomial in . Therefore, is invertible modulo , since is invertible modulo , by hypothesis.

- check whether is invertible modulo and
- compute its inverse modulo in case.

(35) |

(36) |

In other words is a

- ,
- ,
- if then .

(37) |

Now we calculate

(38) |

Now applying Proposition 8 with , and we obtain the first two invariants. In addition, this leads to

(39) |

for . This implies

(40) |

Now, is obtained by one Newton step for inversion (see Algorithm ). Therefore the third invariant follows.

*
*

*
*

2008-01-07