## Rational Function Reconstruction

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

 (86)

Let us denote this problem by . A solution to this problem is also a solution to the following weaker problem: compute a rational function with satisfying

 (87)

We denote this second problem by .

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.
As a result, we obtain an algorithm for solving both problems and .

Theorem 5   Let be the -th row of the Extended Euclidean Algorithm applied to where is minimal such that .
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 .

Proof. First, we observe that are uniquely defined. Indeed, we have and,

 (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 .

Marc Moreno Maza
2008-01-07