**Let
be a field, let
be a polynomial
of degree
.
Given a polynomial
of degree less than
and an integer
, we want to find a rational
function
with
satisfying
**

**We recall that a rational function
is said to be in canonical form if
is monic
and if
.
Clearly, every rational function has a unique canonical form.
**

**The following Theorem 5:
**

- says that problem has always a solution, which can be computed by an algorithm,
- gives a necessary and sufficient condition for a solution of to be a solution of ,
- tells that this condition is also a necessary and sufficient condition for to have a solution.

- The couple is a solution to problem .
- If , then the couple is a solution to problem .
- If is a solution to problem and if is a canonical form, then we have where .
- Problem admits a solution if and only if .

(88) |

Hence, there exists a unique such that we have

(89) |

From Point of Proposition 1 we have

(90) |

leading to . From Proposition 2, we deduce

(91) |

Since holds, we have proved that is a solution to problem . This shows . Now, we prove . We assume that holds. From Point of Proposition 1 we have

(92) |

This implies that is invertible modulo , leading to . Hence, under the assumption , the couple is also a solution to .

Next, we prove . So we consider a solution to such that the fraction is in canonical form. There exists such that we have . Since holds, we can apply Proposition 3. So, let be such that

(93) |

Then, there exists such that and both hold.

If then we have . If then we have .

We prove that holds. If then , and thus , since holds, which implies . If , we can apply Proposition 3 again. Then, there exists such that and both hold. It follows that we have and . Hence, we deduce

(94) |

leading to . Since holds we must have and thus . Therefore, we have proved that holds. This implies

(95) |

Since is in canonical form, we deduce that and hold. This proves . Finally, follows from and .

*
*

2008-01-07