## Search This Blog

### An application of the rational root theorem

This problem is a nice application of the rational root theorem so I present it here together with a solution which I was able to construct.

Problem: Let $f(x) = a_0x^n + a_1x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n$ be a polynomial with integer coefficients ($a_i \in \mathbb{Z}$). Here $n \ge 0, n \in \mathbb{Z}$. The number $\alpha = \frac{p}{q}$ is a rational root of $f(x)$, where $p \in \mathbb{Z}$, $q \in \mathbb{Z}$, $q \ne 0$, $(p,q) = 1$. Prove that $(mq-p)\ |\ f(m)$ for every number $m \in \mathbb{Z}$ such that $(mq-p) \ne 0$.

Solution: We will apply induction on the degree $n$ of $f(x)$.

1) Let $n=0$ i.e. $f(x) = a_0$ is a constant polynomial. Since the number $\alpha$ is a root, it follows that $a_0=0$ i.e. $f(x)$ is the constant $0$. But then $f(m)=0$ for every $m \in \mathbb{Z}$. So for each integer $m$ such that $(mq-p) \ne 0$ we trivially obtain that $(mq-p)\ |\ f(m)$. Thus we proved the statement in the case when $n=0$.

2) Let's also prove the statement when $n=1$. In this case $f(x) = a_0x + a_1$ and $a_0 \ne 0$. From the rational root theorem we get that $q\ |\ a_0$. Then $a_0 = q c_0$ where $c_0 \in \mathbb{Z}$. So $f(x) = c_0 q x + a_1$. Since $\frac{p}{q}$ is a root of $f(x)$ we get $c_0 q (p/q) + a_1 = 0$ which gives us that $c_0 p + a_1 = 0$. Now for $f(x)$ we get the following $f(x) = c_0qx + a_1 = c_0 (qx-p) + (c_0p + a_1)$. But as we saw $(c_0p + a_1) = 0$. So finally $f(x) = c_0 (qx-p) = c_0 (xq - p)$. From this expression we see that $f(m) = c_0 (mq-p)$ for every integer $m$. Then if $m$ is an integer such that $(mq-p) \ne 0$ we obviously get that $(mq-p)\ |\ f(m)$ which is what we wanted to prove.

3) Induction hypothesis. We now assume the statement is true for all polynomials $g(x)$ which satisfy the conditions of the problem statement, and have degrees $\le (n-1)$. Again, the statement is as follows: $(mq-p)\ |\ g(m)$ for every number $m \in \mathbb{Z}$ such that $(mq-p) \ne 0$

4) Now let $f(x) = a_0x^n + a_1x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n$ be a polynomial of degree $n$ (where $n \ge 2$) which satisfies all conditions of the problem statement. Again from the rational root theorem we obtain that $q\ |\ a_0$ so we can write $a_0 = q c_0$, where $c_0 \in \mathbb{Z}$. Then

$f(x) = a_0x^n + a_1x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n =$

$= q c_0 x^n + a_1x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n =$

$= c_0(xq - p) x^{n-1} + (a_1 + c_0p)x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n$

So if we denote $h(x) = (a_1 + c_0p)x^{n-1} + a_2x^{n-2} + ... + a_{n-1}x + a_n$ we obtain that

$f(x) = c_0(xq - p) x^{n-1} + h(x) \tag{*}$

Now we know $p/q$ is a root of $f(x)$. But obviously it's also a root of $c_0(xq - p) x^{n-1}$. So from equality $(*)$ it follows that $p/q$ is also a root of $h(x)$. This means that now $h(x)$ satisfies all the conditions of the problem statement (it has integer coefficients, $p/q$ is its root etc.). Also $h(x)$ has a degree which does not exceed $n-1$. So we can apply to it the induction hypothesis and when we do so, we get that $(mq-p)\ |\ h(m)$ for every integer $m$ such that $(mq - p) \ne 0$. Obviously it's also true that $(mq-p)\ |\ c_0(mq - p) m^{n-1}$ for every integer $m$ such that $(mq - p) \ne 0$. From the last two statements we obtain that $(mq-p)\ |\ (c_0(mq - p) m^{n-1} + h(m))$ for every integer $m$ such that $(mq - p) \ne 0$. But from $(*)$ this expression $(c_0(mq - p) m^{n-1} + h(m))$ is equal to $f(m)$. Thus we obtain that $(mq-p)\ |\ f(m)$ for every integer $m$ such that $(mq - p) \ne 0$. This completes the induction and therefore the statement is now completely proved.

Note 1: In the special case when $m = 1$ we get that $(p-q)\ |\ f(1)$ (unless $q = p = 1$ of course)

Note 2: In the special case when $m = -1$ we get that $(p+q)\ |\ f(-1)$ (unless $q = -p = \pm1$ of course)