# Analytic Number Theory/Partial fraction decomposition

## Existence theorem[edit | edit source]

**Theorem 2.1 (Existence theorem of the partial fraction decomposition)**:

Let be polynomials over a unique factorisation domain, and let , where the are irreducible. Then we may write

- ,

where are polynomials of degree strictly less than and is a polynomial. The term on the right hand side is called the **partial fraction decomposition of **.

**Proof**:

We proceed by induction on . For , the statement is true since by division with remainder, we may write

with to obtain

- ,

and we have reduced the degree of the denominator by one (the latter summand already satisfies the required condition). By repetition of this process, we eventually obtain a denominator of one and thus a polynomial.

Let now the hypothesis be true for , and assume that . Write and . By irreducibility, . Hence, we find polynomials such that . Then

- .

Each of the summands of the last term can by the induction hypothesis be written in the desired form.

## Technique[edit | edit source]

No matter how complicated our fraction of polynomials may be, we can give the partial fraction decomposition in finite time, using easy techniques. The method, which for the sake of simplicity differs from the one given in the above constructive existence proof, goes as follows:

- Split the polynomial into irreducible factors.
- Using division with remainder of by , reduce to the case (the resulting polynomial is allowed in the formula of theorem 2.1).
- Solve the equation given in theorem 2.1 for the (this is equivalent to solving a system of linear equations; namely multiply by and then equate coefficients).

**Theorem 2.2**:

The algorithm given above always terminates and gives the partial fraction decomposition of .

**Proof**: Due to theorem 2.1, in step three we do obtain a system of linear equations which is solvable. Hence follow termination and correctness.