Putnam 2004, Problem B-1

Let $P(x) = c_n x^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_n r, c_n r^2 + c_{n-1} r, c_n r^3 + c_{n-1} r^2 + c_{n-2} r, \ldots, c_n r^n + c_{n-1} r^{n-1} + \cdots + c_1 r
\]
are integers.

Solution:
Let $k$ be an integer, $0 \leq k \leq n-1$. Since $P(r)/r^k = 0$, we have
$$c_n r^{n-k} + c_{n-1} r^{n-k+1} + \cdots + c_{k+1} r$$
$$= -(c_k + c_{k-1} r^{-1} + \cdots + c_0 r^{-k}).$$

Write $r = p/q$ where $p$ and $q$ are relatively prime. Then the left hand side of the above equation can be written as a fraction with denominator $q^{n-k}$, while the right hand side is a fraction with denominator $p^k$. Since $p$ and $q$ are relatively prime, both sides of the equation must be an integer, and the result follows.

**Remark:** If we write $r = a/b$ in lowest terms, then $P(x)$ factors as $(bx - a)Q(x)$, where the polynomial $Q$ has integer coefficients because you can either do the long division from the left and get denominators divisible only by primes dividing $b$, or do it from the right and get denominators divisible only by primes dividing $a$. The numbers given in the problem are none other than $a$ times the coefficients of $Q$. More generally, if $P(x)$ is divisible, as a polynomial over the rationals, by a polynomial $R(x)$ with integer coefficients, then $P/R$ also has integer coefficients; this is known as "Gauss's lemma" and holds in any unique factorization domain.