[This post replaces the previous version from October 12, 2008. The new argument is significantly simpler than the one originally posted.]

I want to present here a Calculus II-level proof that the method of partial fractions decomposition works. I will actually show a more general result, which will greatly simplify the presentation and get rid of most problems of the somewhat awkward formulation below.

We need some notation:

- means .
- , , etc, denote polynomials with real coefficients.

The proof that I show below is algorithmic in nature, meaning that it provides us with a method to find the relevant constants for any given specific polynomials and . The constants we obtain are real numbers.

That the method of partial fractions decomposition works means that we can always find the relevant constants the method requires.

More precisely, I will show the following result:

Theorem.Let be a non-zero polynomial with real coefficients, and let be its factorization intoirreducible factors, so is a constant, and are natural numbers (possibly 0), the numbers are all different, the numbers and are all positive integers (maybe 1), the numbers are all positive, and if , then either or .Let be the degree of . Then, for any polynomial of degree at most , there are unique constants and (some or all of which may be 0) such that

**greatest common divisor**of two polynomials can be expressed as a “

*polynomial combination*” of the two. I would be glad to hear of any possible simplifications you may see.

1. Let’s begin by explaining the factorization

Suppose that is a quadratic polynomial without real roots. We say that is irreducible. We can write or The assumption that has no real roots translates into the statement that . Calling and , this shows that any irreducible quadratic polynomial can be written in the form , where is some constant.

The **fundamental theorem of Algebra**, proved by Gauss, says that any polynomial with real coefficients can be written in a unique way as a product of linear factors and irreducible quadratic factors. This is the only nontrivial fact we are going to assume. Except for it, the proof that follows is essentially self-contained.

The factorization of as shown above comes from applying to the fundamental theorem.

2. If all the coefficients of and all the numbers and are rational, then all the constants are rational numbers as well. This follows from the proof below.

If you know complex numbers, probably you have seen the fundamental theorem of Algebra stated in a slightly different way, namely, that any polynomial is a product of linear factors in a unique way. If we allow the use of complex numbers, so the factorization of does not require any irreducible quadratic terms, the theorem also holds. Now the coefficients of both and can be taken to be complex numbers, we can factor , and we get , where the constants can now be complex numbers. This also follows from the proof below.

In any case, the proof I present does not assume any knowledge of complex numbers, and no actual advantage would come from introducing them in the argument. On the other hand, I do not assume any knowledge of linear algebra either, and although the argument, as presented, does not require any linear algebra, the result seem to naturally lend itself to the language and ideas of this field; I opted for avoiding this approach to make the argument elementary.

3. We need a few preliminary results, that I present now before the proof of the theorem.

**Lemma 1**. If for all , then and .

**Proof.** Call the expression on the left and the expression on the right. Then . Taking derivatives, since , it follows that . Evaluating at 0, we get . Taking derivatives, from it follows that , so or . Continuing this way we get the result.

Notice that the same argument gives that if

for all , then again , , etc. (Now, take derivatives at rather than 0.)

Also, if is an irreducible quadratic and

for constants , then , , , , etc.

To see this, rewrite the given equality as

The left hand side is a linear polynomial and the right hand side is either 0 or a polynomial of degree at least 2, so (by lemma 1) it must be 0, and so and . Divide now by and continue.

**Lemma 2**. Given polynomials and with not the constant 0 polynomial, there are unique polynomials and with such that .

**Proof**. This is just what we get from applying long division. More precisely, if we use long division, we find some polynomials and as wanted. Notice that if and have real coefficients, so do and , and that if and have rational coefficients, again so do and .

There is one final wrinkle, though, since we also need to show that the polynomials and are unique. Accordingly, assume that and are perhaps different polynomials such that and . Then or . If then the left hand side has degree at least , while the right hand side has degree at most , since both and have degree smaller than the degree of . This is clearly impossible. [For example, it follows from Lemma 1 that this cannot happen.] We are then forced to conclude that . So the left hand side is 0, and therefore as well.

Here is a consequence of Lemma 2 that we showed in lecture by a different method: Fix a real number . Let be a polynomial of degree at most . Then we can write as a sum of powers of . To see this, notice that if we divide by , the quotient must be a constant (since the degree of is at most ), and the remainder has degree at most . We can then apply Lemma 2 again and divide by to obtain a constant as quotient and a polynomial of degree at most as remainder. Continuing this way we obtain the result.

The same argument gives also that if for some constant is an irreducible quadratic polynomial, then we can write

where the sum is of course finite and the numbers are constant.

**Definition.** The polynomial is said to be a* greatest common divisor* of the polynomial and if and only if the following two conditions hold:

- (evenly) divides both and .
- If is a polynomial that divides both and , then divides .

There are many greatest common divisors of any two polynomials and , not both equal to 0, since if is an example, then so is . However, except for constant multiples, there is no ambiguity. To find such , it suffices to factor both and into irreducible factors and to take to be the product of their common terms.

**Lemma 3. **Given any polynomials and with greatest common divisor , there are polynomials and such that . If and have rational coefficients, then , and can be chosen with rational coefficients also.

**Proof.** Use lemma 2 repeatedly as follows: We may assume that . Use lemma 2 to find and with , and such that

(1)

If , stop. Otherwise, apply lemma 2 again, this time to and to find and with , and such that

(2)

If , stop. Otherwise, apply lemma 2 to and , etc.

Notice that this process just described must stop, since the polynomials have smaller and smaller degrees. To simplify notation, assume that we find

(3)

, , and finally

(4)

Then (essentially working backwards from these equations)

Here, the first equality follows from (3), the second from (2), the third is a rearrangement of the previous one, the fourth follows from (1), and the last is a rearrangement of the previous one.

In general, this *algorithm* will give a combination of and with polynomial coefficients,

(in this case , , and ). If is a greatest common divisor of and , it follows immediately that divides as well.

Again, working backwards we see that divides by (4), so divides , by (3), so divides , by (2), and also divides , by (1).

In general, the algorithm gives that divides both and , so it divides their greatest common divisor . Since also divides , the only way this is possible is for and to be multiples of each other by a constant, and so is a greatest common divisor of and .

The above is the **Euclidean algorithm** and dates back to Euclid’s *Elements*. The same argument gives that the greatest common divisor of two natural numbers and is a linear combination of and with integer coefficients .

Notice, however, that there is no uniqueness here. For if then also for any polynomial .

4. We are now ready to prove the theorem.

Begin by writing where the have no common factors. Let be any polynomial (whose degree may be larger than the degree of ).

I **claim** that we can write

where are polynomials and for all

The argument to follow is an example of **mathematical induction**. We argue that the claim is true if , and then show how knowing the truth of the claim for factors gives also the truth for factors. Combining these two bits of information, it follows that the claim is true, no matter how many factors has.

For the result follows from lemma 2: We have and we can write for some polynomials and with , so

which is precisely what the claim says when .

Assume the result is true when is a product of polynomials with (pairwise) no common factors, and assume where the have no common factors.

Call , so and have no common factors either. It follows from lemma 3 that we can find polynomials and such that

Then

Applying the case of the claim, we find polynomials and with such that

Applying the claim with in place of and in place of , since we are assuming that the result follows for products of many factors, swe have that there are polynomials and with such that

Combining these two facts and setting , we have the claim.

5. In the above, we could have or , in which case we can use the observation following lemma 2 above, to continue further: Say . As explained after lemma 2, we can write for some constants , the sum has only many factors since

But then

We obtain a similar expansion if is a power of an irreducible quadratic, but now instead of the constant coefficients we obtain linear factors .

Doing this for each factor gives the theorem. (We still need to see that if then what we called above must in fact be 0, and that we have uniqueness.)

6. We are almost done. The only bit of the theorem that remains to be checked is the claim that the constants we find are unique, meaning that there is only one possible decomposition of the sort claimed in the theorem.

We actually show that there is uniqueness in the expressions found in item 4. For this, suppose we have

for some polynomials with .

Then

for some polynomial that necessarily has degree less than the degree of . But the only way this is possible is if , so . (This also shows that if .)

Now argue by induction on . The case is trivial, since then we have , so .

Assuming the result for , now consider with many factors, so we can write

for some polynomial of smaller degree than . Since and have no common factors and

we must have that actually divides . Since is of smaller degree, the only possibility is that , so . But then we also have

and the inductive assumption gives us that .

7. Finally, using lemma 1 (or rather, lemma 1 and the observations following it), we complete the proof of uniqueness, since if

equals a similar expression with possibly different coefficients, the argument of item 6 gives that we must have that the expressions with powers of are the same, and then lemma 1 gives that their coefficients are the same, and the same follows for the expressions with powers of a fixed irreducible quadratic.

And with this, we are done.

Please let me know of typos, and whether there are parts of the argument above that are not explained clearly or that you are not sure you understand completely; it may be a good idea to first work through the argument with a few examples, since this may help clarify what it is that we are doing.

To conclude, let me point out that even though the proof above provides an algorithm for finding the required constants, I believe (but haven’t checked that) the methods discussed in class are somewhat faster. It turns out that the argument above dates back to Hermite. In any case, the point of the argument above is not so much to give yet another method for finding the constants of the partial fractions decomposition, as it is to provide us with evidence that, whichever method we use, we can be assured that it will be successful, and we will be able to find some such decomposition.

Also, notice the argument becomes very simple by just arguing about an arbitrary `decomposition’ of into pieces with no common factors, so the result one is after becomes a very particular case. And the method is quite general, for example, it works if and are numbers and we measure with absolute value rather than degree, so we get: If is the factorization of into prime numbers, and is an integer, then there is a unique way of writing

where are integers, , and ; moreover, there is a unique way of writing

for an integer with as a sum of fractions with . This is usually called the *-adic decomposition* of .

[…] the method of partial fractions decomposition, we see that Notice that , […]

[…] a look at Talman’s paper; see here); but it won’t include the proof that the method of partial fractions decomposition works. For 275, you may want to review the polar expression of the Laplacian and how to derive it. […]

[Comment by Chingyun Hsu on Jun 18, 2014 @ 7:20, at the old site. I’ve corrected the typo.]

Hi! I think there might be a typo here:

Assuming the result for , now consider with many factors, so we can write

It should be

[…] a look at Talman’s paper; see here); but it won’t include the proof that the method of partial fractions decomposition works. For 275, you may want to review the polar expression of the Laplacian and how to derive it. […]