40 CHAPTER 2. THE REAL AND COMPLEX NUMBERS
This is the partial fractions expansion of the rational function. Actually carrying outthis computation may be impossible, but this shows the existence of such a partialfractions expansion. Hint: You might induct on the sum of the mi and use Proposition2.14.6.
20. One can give a fairly simple algorithm to find the g.c.d., greatest common divisorof two polynomials. The coefficients are in some field. For us, this will be eitherthe real, rational, or complex numbers. However, in general, the algorithm for longdivision would be carried out in whatever field includes the coefficients. Explain thefollowing steps. Let r0 (λ ) ,r1 (λ ) be polynomials with the degree of r0 (λ ) at leastas large as the degree of r1 (λ ). Then do division.
r0 (λ ) = r1 (λ ) f1 (λ )+ r2 (λ )
where r2 (λ ) has smaller degree than r1 (λ ) or else is 0. If r2 (λ ) is 0, then the g.c.d.of r1 (λ ) ,r0 (λ ) is r1 (λ ). Otherwise, l (λ )/r0 (λ ) ,r1 (λ ) if and only if
l (λ )/r1 (λ ) ,r2 (λ ) .
Do division againr1 (λ ) = r2 (λ ) f2 (λ )+ r3 (λ )
where deg(r3 (λ ))< deg(r2 (λ )) or r3 (λ ) is 0. Then l (λ )/r2 (λ ) ,r3 (λ ) if and onlyif l (λ ) divides both r1 (λ ) and r2 (λ ) if and only if l (λ )/r0 (λ ) ,r1 (λ ) . If r3 (λ ) = 0,then r2 (λ )/r2 (λ ) ,r1 (λ ) so also r2 (λ )/r0 (λ ) ,r1 (λ ) and also, if
l (λ )/r0 (λ ) ,r1 (λ ) ,
then l (λ )/r1 (λ ) ,r2 (λ ) and in particular, l (λ )/r1 (λ ) so if this happens, then r2 (λ )is the g.c.d. of r0 (λ ) and r1 (λ ) . Continue doing this. Eventually either rm+1 (λ ) = 0or has degree 0. If rm+1 (λ ) = 0, then rm (λ ) multiplied by a suitable scalar to makethe result a monic polynomial is the g.c.d. of r0 (λ ) and r1 (λ ). If the degree is 0,then the two polynomials r0 (λ ) ,r1 (λ ) must be relatively prime. It is really signif-icant that this can be done because fundamental theorems in linear algebra dependon whether two polynomials are relatively prime having g.c.d. equal to 1. In thisapplication, it is typically a question about a polynomial and its derivative.
21. Find the g.c.d. for(x4 +3x2 +2
),(x2 +3
).
22. Find g.c.d. of(x5 +3x3 + x2 +3
),(x2 +3
).
23. Find the g.c.d. of(x6 +2x5 + x4 +3x3 +2x2 + x+2
),(x4 +2x3 + x+2
).
24. Find the g.c.d. of(x4 +3x3 +2x+1
),(4x3 +9x2 +2
). If you do this one by hand, it
might be made easier to note that the question of interest is resolved if you multiplyeverything with a nonzero scalar before you do long division.
25. Prove the pigeon hole principle by induction.