The rational root theorem and a Putnam question
I came across the following Putnam question yesterday:
B1 Let be a polynomial with integer coefficients. Suppose that is a rational number such that . Show that the numbers
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 is called reduced if , , and .
Theorem (rational root theorem): Suppose that is a polynomial with integer coefficients :
If the reduced fraction is a root of , then and .
Proof: Since is a root of , we have
After multiplying by we obtain
Now subtract and factor out the factor on the left side:
Since the left-hand side is a product of two integers, is a divisor of the left-hand side, so it is also a divisor of the right hand side. So we have . Since is a reduced fraction, we have . It follows that . Switching the roles of and , and and , we can deduce that in an analogous way.
Note: If the polynomial 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 and are fractions with and , then and are integers.
Proof: Let be the reduced form of , so that we have . Since is the reduced form of , there exists an such that and . Likewise, there exists an such that and . Now we have . Since , it follows that . So we have .
Now, we’re ready to provide the proof that the question asks for.
Theorem: Suppose that is a polynomial with integer coefficients :
If is a rational root of the , then the numbers
Proof: We prove that is an integer using induction. The base case holds by the rational root theorem. For the induction step, assume that is an integer for all . Write as a reduced fraction . Since is a root of we have
Multiply by and subtract from both sides, and we get:
By the induction assumption, the right side is an integer. To emphasize this, substitute . Then, subtract from both sides and multiply by :
We now invoke the lemma, and conclude that the right-hand side, which equals must also be an integer. This completes the induction step.