 |
 |
Problem Posts |  |
 |
QUESTION
(PMO 2012-2) Let $f$ be a polynomial function with integer coefficients and $p$ be a prime number. Suppose there are at least four distinct integers satisfying $f\left(x\right)=p$. Show that $f$ does not have integer zeroes.
(PMO 2012-2) Let $f$ be a polynomial function with integer coefficients and $p$ be a prime number. Suppose there are at least four distinct integers satisfying $f\left(x\right)=p$. Show that $f$ does not have integer zeroes.
Laconic Solution Sketch Get the most obvious auxiliary polynomial.
Discussion
For many people this will probably be the easiest problem in the paper. First, we need a very basic theorem:
THEOREM
Given a polynomial $f\left(x\right)$, iff $f\left(a\right)=0$, then $\left(x-a\right)$ divides $f\left(x\right)$.
Given a polynomial $f\left(x\right)$, iff $f\left(a\right)=0$, then $\left(x-a\right)$ divides $f\left(x\right)$.
Now we want to leverage the Root Theorem along with what we know about $f\left(x\right)$. There are at least two approaches to consider:
Route 1: Jump to Contradiction
One approach would be to apply the theorem directly. Suppose $f\left(x\right)$ has an integer zero $n$, then $\left(x-n\right)$ is a factor of $f\left(x\right)$. That means that \[ f\left(x\right)=q\left(x\right)\left(x-n\right) \] where $q\left(x\right)$, the quotient, is a polynomial with integer coefficients. Now let's plug in $x=a_{1}$. We would have $p=f\left(a_{1}\right)=q\left(a_{1}\right)\left(a_{1}-n\right)$. Our left hand side is a prime number, and $q\left(a_{1}\right)$ and $\left(a_{1}-n\right)$ are integers. This means that $\left(a_{1}-n\right)$ is a divisor of a prime number, so $\left(a_{1}-n\right)$ is among $\left\{ \pm1,\pm p\right\} $.This fact, taken in itself, isn't very interesting. But when we compound that with the fact that the same has to occur for $\left(a_{2}-n\right)$, $\left(a_{3}-n\right)$, and $\left(a_{4}-n\right)$, something interesting happens: these four numbers have to all be different, and each can be one of four numbers! So that means that the four $a_{i}$ have to be $n+1$, $n-1$, $n+p$, $n-p$.
If there was an $a_{5}$ we'd have a contradiction, because recall that all the $a_{i}$ have to be different. Unfortunately, we're only sure that four $a_{i}$ exist, so we can't really conclude anything. For me this looks like a dead end.
Route 2: Auxiliary Polynomial
We have to be a bit more subtle in using the Root Theorem. Ideally we'd want a polynomial to be zero somewhere. Unfortunately we aren't given that information with $f\left(x\right)$. However, we can set an auxiliary polynomial $g\left(x\right)$ to be exactly $f\left(x\right)-p$. That way, there are at least four distinct integers satisfying $g\left(x\right)=f\left(x\right)-p=0$.Since it's getting tiring saying ``at least four distinct integers'', let's call the four distinct integers $a_{1}$, $a_{2}$, $a_{3}$, $a_{4}$. There could be more, but whatever we have to prove cannot depend on those extra ones. So we have $g\left(a_{1}\right)=0$, $g\left(a_{2}\right)=0$, and so on.
We can use the Root Theorem now: Since $g\left(a_{1}\right)=0$, we must have $\left(x-a_{1}\right)$ as a factor of $g\left(x\right)$. The same goes for $\left(x-a_{2}\right)$, $\left(x-a_{3}\right)$, and so on. This means that \[ g\left(x\right)=h\left(x\right)\left(x-a_{1}\right)\left(x-a_{2}\right)\left(x-a_{3}\right)\left(x-a_{4}\right) \] where $h\left(x\right)$ is the quotient polynomial (which also has integer coefficients!). Don't forget that we have to put $h\left(x\right)$ there, since $g\left(x\right)$ could have other polynomial factors apart from the four. Also note that at this point, we needed the fact that $a_{1}$, $a_{2}$, and so on are all different from each other.
This is all nice, but how does it bring us to what we want to show? Remember we want to show that $f\left(x\right)$ has no integer zeroes. That means no integer should satisfy $f\left(x\right)=0$, or equivalently $g\left(x\right)=-p$. But when we look at the equation above, we've shown that for any integer $n$, $g\left(n\right)$ is the product of five integers, four of which have to be different! There's no way we can write $-p$ like that, so we're done.
SOLUTION
Let the four distinct integers be $a_{1},a_{2},\ldots,a_{4}$ , and let $g\left(x\right):= f\left(x\right)-p$ , so that for $i=1,2,\ldots,4$ , we have $g\left(a_{i}\right)=0$. Then $\left(x-a_{i}\right)$ divides $g\left(x\right)$, and since the $a_{i}$ are distinct we have$g\left(x\right)=h\left(x\right)\left(x-a_{1}\right)\left(x-a_{2}\right)\left(x-a_{3}\right)\left(x-a_{4}\right)$ where $h\left(x\right)$ is a polynomial with integer coefficients. Now suppose for the sake of contradiction $f\left(x\right)$ has an integer root $n$ . Then \begin{eqnarray*} -p & = & f\left(n\right)-p\\ & = & g\left(n\right)\\ & = & h\left(n\right)\left(n-a_{1}\right)\left(n-a_{2}\right)\left(n-a_{3}\right)\left(n-a_{4}\right) \end{eqnarray*} Now we must have $h\left(n\right),\left(n-a_{i}\right)\in\left\{ \pm1,\pm p\right\} $ , and such that either $p$ or $-p$ (but not both or neither) shows up in the above product, and so that the $\left(n-a_{i}\right)$ are distinct. The five values cannot be so allocated, hence we have a contradiction.
Let the four distinct integers be $a_{1},a_{2},\ldots,a_{4}$ , and let $g\left(x\right):= f\left(x\right)-p$ , so that for $i=1,2,\ldots,4$ , we have $g\left(a_{i}\right)=0$. Then $\left(x-a_{i}\right)$ divides $g\left(x\right)$, and since the $a_{i}$ are distinct we have$g\left(x\right)=h\left(x\right)\left(x-a_{1}\right)\left(x-a_{2}\right)\left(x-a_{3}\right)\left(x-a_{4}\right)$ where $h\left(x\right)$ is a polynomial with integer coefficients. Now suppose for the sake of contradiction $f\left(x\right)$ has an integer root $n$ . Then \begin{eqnarray*} -p & = & f\left(n\right)-p\\ & = & g\left(n\right)\\ & = & h\left(n\right)\left(n-a_{1}\right)\left(n-a_{2}\right)\left(n-a_{3}\right)\left(n-a_{4}\right) \end{eqnarray*} Now we must have $h\left(n\right),\left(n-a_{i}\right)\in\left\{ \pm1,\pm p\right\} $ , and such that either $p$ or $-p$ (but not both or neither) shows up in the above product, and so that the $\left(n-a_{i}\right)$ are distinct. The five values cannot be so allocated, hence we have a contradiction.
