Wednesday, October 18, 2006

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)$.