(8) |

(9) |

- ,
- .

(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

A solution of this equation is

(16) |

This proves the claim of the theorem.

(17) |

- ,
- ,
- .

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

So the induction hypothesis leads to

(21) |

Hence there exist polynomials such that

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

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

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

*
*

2008-01-07