The rational root theorem and a Putnam question

I came across the following Putnam question yesterday:

B1 Let P(x)=cnxn+cn−1x.n−1..+c0P(x) = c_n x^n + c_{n - 1} x^{n - 1} _ ... + c_0 be a polynomial with integer coefficients. Suppose that rr is a rational number such that P(r)=0P(r) = 0. Show that the nn numbers
cnr,cnr2+cn−1r,cnr3+cn−1r2+cn−2r,...,cnrn+cn−1rn−1+...+c1rc_nr, c_nr^2 + c_{n - 1}r, c_nr^3 + c_{n - 1}r^2 + c_{n - 2}r, ..., c_nr^n + c_{n - 1} r^{n - 1} + ... + c_1r

are integers.

If you’re familiar with the rational root theorem you will probably see a connection. Indeed, the proof that the question asks for is along the same lines.

I have to admit I didn’t remember the proof of the rational root theorem. It’s one of those proofs that’s not very hard once you know the trick, but if you don’t know the trick, you can spend quite some time without finding the proof. It took me a while to find it again, so I will document it here for myself.

Definition: A fraction pq\frac{p}{q} is called reduced if p∈Zp \in \mathbb{Z}, q∈Nq \in \mathbb{N}, and gcd⁡(p,q)=1\gcd(p, q) = 1.

Theorem (rational root theorem): Suppose that ff is a polynomial with integer coefficients c0,c1,...,cn∈Zc_0, c_1, ..., c_n \in \mathbb{Z}:
f(x)=c0+c1x+...cnxnf(x) = c_0 + c_1 x + ... c_n x^n

If the reduced fraction pq\frac{p}{q} is a root of ff, then p∣c0p | c_0 and q∣cnq | c_n.

Proof: Since pq\frac{p}{q} is a root of ff, we have
c0+c1pq+...+cn(pq)n=0c_0 + c_1 \frac{p}{q} + ... + c_n (\frac{p}{q})^n = 0

After multiplying by qnq^n we obtain

c0qn+c1qn−1p+...+cnpn=0c_0 q^n + c_1 q^{n - 1}p + ... + c_n p^n = 0

Now subtract c0qnc_0 q^n and factor out the factor pp on the left side:

p(c1qn−1+c2qn−2p+...cnpn−1)=−c0qnp(c_1q^{n - 1} + c_2 q^{n - 2} p + ... c_n p^{n - 1}) = -c_0 q^n

Since the left-hand side is a product of two integers, pp is a divisor of the left-hand side, so it is also a divisor of the right hand side. So we have p∣c0qnp | c_0 q^n. Since pq\frac{p}{q} is a reduced fraction, we have gcd⁡(p,q)=1\gcd(p, q) = 1. It follows that p∣c0p | c_0. Switching the roles of pp and qq, and c0c_0 and cnc_n, we can deduce that q∣cnq | c_n in an analogous way. □\square

Note: If the polynomial ff has rational coefficients, it can easily transformed to a polynomial with the same roots and integer coefficients by multiplying it by the least common multiple of all the denominators.

The proof that the Putnam question asks for can be derived in a similar way. In the proof we will use the following lemma:

Lemma: If ab\frac{a}{b} and cd\frac{c}{d} are fractions with ab=cd\frac{a}{b} = \frac{c}{d} and gcd⁡(b,d)=1\gcd(b,d) = 1, then ab\frac{a}{b} and cd\frac{c}{d} are integers.

Proof: Let pq\frac{p}{q} be the reduced form of ab\frac{a}{b}, so that we have pq=ab=cd\frac{p}{q} = \frac{a}{b} = \frac{c}{d}. Since pq\frac{p}{q} is the reduced form of ab\frac{a}{b}, there exists an m∈Nm \in \mathbb{N} such that a=mpa = mp and b=mqb = mq. Likewise, there exists an n∈Nn \in \mathbb{N} such that c=npc = np and d=nqd = nq. Now we have gcd⁡(b,d)=gcd⁡(mq,nq)=1\gcd(b, d) = \gcd(mq, nq) = 1. Since q∣gcd⁡(mq,nq)q | \gcd(mq, nq), it follows that q=1q = 1. So we have ab=cd=pq=p\frac{a}{b} = \frac{c}{d} = \frac{p}{q} = p. □\square

Now, we’re ready to provide the proof that the question asks for.

Theorem: Suppose that ff is a polynomial with integer coefficients c0,c1,...,cn∈Zc_0, c_1, ..., c_n \in \mathbb{Z}:
f(x)=c0+c1x+...cnxnf(x) = c_0 + c_1 x + ... c_n x^n

If rr is a rational root of the ff, then the numbers
cnr,cnr2+cn−1r,cnr3+cn−1r2+cn−2r,...,cnrn+cn−1rn−1+...+c1rc_n r, c_n r^2 + c_{n - 1} r, c_n r^3 + c_{n - 1} r^2 + c_{n - 2} r, ..., c_n r^n + c_{n - 1} r^{n - 1} + ... + c_1 r

are integers.

Proof: We prove that ∑k=1mcn+1−krk\sum^m_{k = 1} c_{n + 1 - k} r^k is an integer using induction. The base case m=1m = 1 holds by the rational root theorem. For the induction step, assume that cnrm+...+cn+1−mrc_n r^m + ... + c_{n + 1 - m} r is an integer for all m≤Mm \leq M. Write rr as a reduced fraction pq\frac{p}{q}. Since pq\frac{p}{q} is a root of ff we have
c0+c1pq+...+cn(pq)n=0c_0 + c_1 \frac{p}{q} + ... + c_n (\frac{p}{q})^n = 0

Multiply by (qp)n−M(\frac{q}{p})^{n - M} and subtract cnrM+cn−1rM−1+...+cn+1−Mrc_n r^M + c_{n - 1} r^{M - 1} + ... + c_{n + 1 - M}r from both sides, and we get:
c0qn−M+c1pqn−M−1+...+cn−M−1pn−M−1q+cn−Mpn−Mpn−M\frac{c_0 q^{n - M} + c_1 p q^{n - M - 1} + ... + c_{n - M - 1}p^{n - M - 1}q + c_{n - M}p^{n - M}}{p^{n - M}}
=−(cnrM+cn−1rM−1+...+cn+1−Mr)= -(c_n r^M + c_{n - 1} r^{M - 1} + ... + c_{n + 1 - M}r)

By the induction assumption, the right side is an integer. To emphasize this, substitute k:=cnrM+cn−1rM−1+...+cn+1−Mrk := c_n r^M + c_{n - 1} r^{M - 1} + ... + c_{n + 1 - M}r. Then, subtract cn−Mc_{n - M} from both sides and multiply by r=pqr = \frac{p}{q}:
c0qn−M+c1pqn−M−1+...+cn−M−1pn−M−1qpn−M=−(k+cn−M)pq\frac{c_0 q^{n - M} + c_1 p q^{n - M - 1} + ... + c_{n - M - 1}p^{n - M - 1}q}{p^{n - M}} = -\frac{(k + c_{n - M})p}{q}

We now invoke the lemma, and conclude that the right-hand side, which equals cnrM+1+cn−1rM+...+cn−Mrc_n r^{M + 1} + c_{n - 1} r^M + ... + c_{n - M}r must also be an integer. This completes the induction step. □\square