\documentstyle[12pt,twoside]{article}
\input{macros-course}

\newcommand{\dgr}[1]{\hbox{degree}(#1)}
\newcommand{\mod}{\hbox{mod}}


\begin{document}

Charles-- my apologies for the mix-up on this proof. It's not terribly
original, but it is mine-- about two years ago I got sick of having
never seen a proof, so I wrote this up. And then I tried to massively
oversimplify it when I explained it to you. This should fix it.

So, recall the setup. We have two polynomials, $p$ and $q$ in a single
variable, $x$, and $\dgr p <\dgr q $. 
Without loss of generality, $q$ is monic,
so suppose $q$ factors into a product \[\prod_{i=1}^m (x-\gamma_i)^{d_i},\]
with all $\gamma_i$ distinct, and all $d_i$ positive.

Now, if $i\ne j$, then $(x-\gamma_i)^{d_i}$ and $(x-\gamma_j)^{d_j}$ are
relatively prime, so we can write 
\[ r_{i,j} (x-\gamma_j)^{d_j} + s_{i,j} (x-\gamma_i)^{d_i}   = 1 \]
for some polynomials $r_{i,j}$ and $s_{i,j}$.
The important point here is that 
\[ r_{i,j}  (x-\gamma_j)^{d_j} = 
          \left\{ {0\ \mod\ (x-\gamma_j)^{d_j} \atop
                  1\ \mod\ (x-\gamma_i)^{d_i} } \right.  \]
for $i\ne j$.

So we now rewrite the long summation formula that I did for you at the board.
Let's call it $w$. We have
\[w(x)=\sum_{i=1}^m  (p\ \mod\ (x-\gamma_i)^{d_i})
     \prod_{j=1\atop j\ne i}^n r_{i,j}  (x-\gamma_j)^{d_j} \quad. \]

Now, examine $w\ \mod\ (x-\gamma_l)^{d_l}$. If $i\ne l$, the $i$th term
in the summation contains the factor $r_{i,l}  (x-\gamma_l)^{d_l}$ and
hence vanishes. Thus the summation (modulo $(x-\gamma_l)^{d_l}$) reduces
to \[ (p\ \mod\ (x-\gamma_l)^{d_l})
     \prod_{j=1\atop j\ne l}^n r_{l,j}  (x-\gamma_j)^{d_j} \quad. \]
But this (modulo $(x-\gamma_l)^{d_l}$) is actually
\[ (p\ \mod\ (x-\gamma_l)^{d_l}) \quad. \]
since  $r_{l,j}  (x-\gamma_j)^{d_j} = 1\ ( \mod\ (x-\gamma_l)^{d_l})$.

Since $w = p$ \quad (modulo  $(x-\gamma_l)^{d_l}$) for all $l=1\ldots m$,
the Chinese Remainder Theorem tells us that $w = p + tq$ for some polynomial
$t$. Dividing by $q$ yields
\[{p\over q} + t = \sum_{i=1}^m  (p\ \mod\ (x-\gamma_i)^{d_i})
     \left(\prod_{j=1\atop j\ne i}^n r_{i,j}\right)  
      {1\over (x-\gamma_i)^{d_i}} \quad. \]
Now things get a bit messy formula-wise, but the idea (if you don't
want an exact formula) is that the left-hand side and right hand side
are both rational functions--get rid of the non-fractional part on
each side, and you're left with an identity describing $p/q$ as a sum
of $m$ ``proper'' rational functions with denominators of the form
$(x-\gamma_i)^{d_i}$. So let's see an explicit formula. For $i=1\ldots m$,
write \[ (p\ \mod\ (x-\gamma_i)^{d_i})
     \left(\prod_{j=1\atop j\ne i}^n r_{i,j}\right) 
= T_i + {R_i\over  (x-\gamma_i)^{d_i}}\] where 
$R_i = (p\ \mod\ (x-\gamma_i)^{d_i})
     \left(\prod_{j=1\atop j\ne i}^n r_{i,j}\right) 
\ \mod\  (x-\gamma_i)^{d_i}$ and hence has degree less than $d_i$.
Thus we find 
\[{p\over q} + t = \sum_{i=1}^m \left( T_i +  
      {R_i\over (x-\gamma_i)^{d_i}} \right) \]
with $\dgr p  < \dgr q$ and $\dgr {R_i} < d_i$ for $i=1\ldots m$.
This implies (pick your favorite proof--mine's purely algebraic)
that the negative degree parts of the left-hand side and the right-hand
side must be equal. Thus 
\[{p\over q} =  \sum_{i=1}^m {R_i\over (x-\gamma_i)^{d_i}} \quad\qed\]

This is a constructive process (at least if you've got an extended
euclidean algorithm lying around), so let's do a brief example, namely
a partial fractions decomposition of
$x\over x^2 (x+1)^2$.
A brief check verifies that the $r_{i,j}$'s required are
$1-2x$ and $2x+3$. So the expansion (up to additive factors of
$x^2 (x+1)^2$\ \ ) of $x$ is
\[ x (1-2x) (1+x)^2 + x(2x+3)x^2 \quad.\]
Dividing by $x^2 (x+1)^2$ yields
\[ {x (1-2x) \over x^2} + {x(2x+3) \over (1+x)^2}\]
which, expanding numerators, is
\[ {-2x^2+x \over x^2} + {2x^2+3x \over (1+x)^2}\quad. \]
After reducing each numerator modulo its denominator, the proof above
yields the identity
\[ {x \over x^2} + {-x-2\over (1+x)^2} = x \]
which can be verified directly.

\end{document}



