Problem: (2004 Putnam - B1) Let $ P(x) = c_nx^n+c_{n-1}x^{n-1}+\cdots+c_0 $ be a polynomial with integer coefficients. Suppose that $ r $ is a rational number such that $ P(r) = 0 $. Show that the $ n $ numbers
$ c_nr, c_nr^2+c_{n-1}r, c_nr^3+c_{n-1}r^2+c_{n-2}r, \ldots, c_nr^n+c_{n-1}r^{n-1}+\cdots+c_1r $
are integers.
Solution: Well rational numbers only really have one good way of being handled - rewrite $ r $ as $ \frac{p}{q} $ for relatively prime integers $ p, q $. We then know that
$ P(r) = \frac{c_np^n+c_{n-1}p^{n-1}q+\cdots+c_0q^n}{q^n} = 0 $
so the numerator is zero. Also, we may write the $ n $ integers as
$ \frac{c_np^n+c_{n-1}p^{n-1}q+\cdots+c_{k+1}p^{k+1}q^{n-(k+1)}}{p^kq^{n-k} $
for $ k = 0, 1, \ldots, n-1 $ (from substituting $ r = \frac{p}{q} $ and finding a common denominator). Notice that
$ c_np^n+c_{n-1}p^{n-1}q+\cdots+c_{k+1}p^{k+1}q^{n-(k+1)} \\ = -(c_kp^kq^{n-k}+c_{k-1}p^{k-1}q^{n-(k-1)}+\cdots+c_0q^n) $
from $ P(r) = 0 $. The LHS gives us that the quantity is divisible by $ p^k $ (since every term has a power of $ p $ greater than or equal to $ k $) and the RHS gives us that the quantity is divisible by $ q^{n-k} $ (since every term has power of $ q $ greater than or equal to $ n-k $). Since $ p $ and $ q $ are relatively prime, however, we must have
$ (p^kq^{n-k}) | (c_np^n+c_{n-1}p^{n-1}q+\cdots+c_{k+1}p^{k+1}q^{n-(k+1)}) $
or
$ \frac{c_np^n+c_{n-1}p^{n-1}q+\cdots+c_{k+1}p^{k+1}q^{n-(k+1)}}{p^kq^{n-k} $
is an integer for $ k = 0, 1, \ldots, n-1 $, as desired. QED.
--------------------
Comment: Actually more difficult than I expected from a B1 on the Putnam; it required solid knowledge of how to deal with rational numbers and roots of polynomials. That said, a good number of people got it right, so maybe I just messed around for a bit too long. In any case, this is a problem worth learning how to do.
--------------------
Practice Problem: Prove that the remainder of $ P(x) $ when divided by $ x-r $ is $ P(r) $.
No comments:
Post a Comment