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..+c0 be a polynomial with integer coefficients. Suppose that r is a rational number such that P(r)=0. Show that the n numbers
cnr,cnr2+cn−1r,cnr3+cn−1r2+cn−2r,...,cnrn+cn−1rn−1+...+c1r
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 qp is called reduced if p∈Z, q∈N, and gcd(p,q)=1.
Theorem (rational root theorem): Suppose that f is a polynomial with integer coefficients c0,c1,...,cn∈Z:
f(x)=c0+c1x+...cnxn
If the reduced fraction qp is a root of f, then p∣c0 and q∣cn.
Proof: Since qp is a root of f, we have
c0+c1qp+...+cn(qp)n=0
After multiplying by qn we obtain
c0qn+c1qn−1p+...+cnpn=0
Now subtract c0qn and factor out the factor p on the left side:
p(c1qn−1+c2qn−2p+...cnpn−1)=−c0qn
Since the left-hand side is a product of two integers, p is a divisor of the left-hand side, so it is also a divisor of the right hand side. So we have p∣c0qn. Since qp is a reduced fraction, we have gcd(p,q)=1. It follows that p∣c0. Switching the roles of p and q, and c0 and cn, we can deduce that q∣cn in an analogous way. □
Note: If the polynomial f 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 ba and dc are fractions with ba=dc and gcd(b,d)=1, then ba and dc are integers.
Proof: Let qp be the reduced form of ba, so that we have qp=ba=dc. Since qp is the reduced form of ba, there exists an m∈N such that a=mp and b=mq. Likewise, there exists an n∈N such that c=np and d=nq. Now we have gcd(b,d)=gcd(mq,nq)=1. Since q∣gcd(mq,nq), it follows that q=1. So we have ba=dc=qp=p. □
Now, we’re ready to provide the proof that the question asks for.
Theorem: Suppose that f is a polynomial with integer coefficients c0,c1,...,cn∈Z:
f(x)=c0+c1x+...cnxn
If r is a rational root of the f, then the numbers
cnr,cnr2+cn−1r,cnr3+cn−1r2+cn−2r,...,cnrn+cn−1rn−1+...+c1r
are integers.
Proof: We prove that ∑k=1mcn+1−krk is an integer using induction. The base case m=1 holds by the rational root theorem. For the induction step, assume that cnrm+...+cn+1−mr is an integer for all m≤M. Write r as a reduced fraction qp. Since qp is a root of f we have
c0+c1qp+...+cn(qp)n=0
Multiply by (pq)n−M and subtract cnrM+cn−1rM−1+...+cn+1−Mr from both sides, and we get:
pn−Mc0qn−M+c1pqn−M−1+...+cn−M−1pn−M−1q+cn−Mpn−M
=−(cnrM+cn−1rM−1+...+cn+1−Mr)
By the induction assumption, the right side is an integer. To emphasize this, substitute k:=cnrM+cn−1rM−1+...+cn+1−Mr. Then, subtract cn−M from both sides and multiply by r=qp:
pn−Mc0qn−M+c1pqn−M−1+...+cn−M−1pn−M−1q=−q(k+cn−M)p
We now invoke the lemma, and conclude that the right-hand side, which equals cnrM+1+cn−1rM+...+cn−Mr must also be an integer. This completes the induction step. □