8
$\begingroup$

Here is a question from Canada MO:

Let $P(x)$ be a polynomial with integer coefficients. If $P(0)$ and $P(1)$ are both odd, show that $P(x)$ has no integer roots.

My idea to solve the problem is following:

Let $P(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0$ be the polynomial. Then $P(0)=a_0$ and $P(1)=a_n+a_{n-1}+\dots+a_0=k$ where $a_0$ and $k$ is odd. We assume that there exists an integer root $r$. Then $r\vert a_0$ by rational root theorem. In other words, $r$ is odd. Now let $P(x)=(x-1)Q(x)+k$. Then $P(-r)=(-r-1)Q(-r)+k=0\\ \implies -(r+1)Q(-r)=-k.$
Since $k$ is odd, $r+1$ must be odd or $r$ must be even which leads to a contradiction. Hence, $P(x)$ can't have an integer root.

Is my above solution correct? Also can we generalize the result of the problem, that is, for example if $P(0)$, $P(1)$ and $P(2)$ are not divisible by $3$ can we say $P(x)$ has no integer roots?

$\endgroup$
3
  • 6
    $\begingroup$ Easier: We have $P(a+bn)\equiv P(a)\pmod{n}$ for all $a,b\in\mathbb{Z}$. This also proves your generalised result. $\endgroup$ Commented Sep 12, 2021 at 6:05
  • $\begingroup$ Can you please add the year the question was asked. $\endgroup$
    – blackened
    Commented Sep 12, 2021 at 15:25
  • 1
    $\begingroup$ @blackened I don't know the exact year. But I am pretty sure this is an old one and from Canadian mathematical olympiad. You can check the years 1970 to 1980 if you really need the exact year. $\endgroup$
    – Oshawott
    Commented Sep 12, 2021 at 15:52

2 Answers 2

8
$\begingroup$

In your solution, I believe you should have written: $$P(r) = (r-1)Q(r) + k$$ With that adjustment, the solution works perfectly. To generalize, you could try to show: $$(x-y) \mid (P(x)-P(y))$$ (To do this, you could start out by showing it for $P(x)=x^n$, and then generalize it to all polynomials). Once you do this, by substituting $y=0,1$), you can see that for all $x \in \mathbb{Z}$: $$x \mid (P(x)-P(0))$$ $$(x-1) \mid (P(x)-P(1))$$ Since one of $x$ and $x-1$ is even, one of $P(x)-P(0)$ and $P(x)-P(1)$ must be even. Since both $P(0)$ and $P(1)$ are odd, $P(x)$ must be odd as well. Hence, $P(x) \neq 0$ for any $x \in \mathbb{Z}$. This approach can be generalized as you wanted, give it a shot!

$\endgroup$
2
$\begingroup$

Suppose $P(n)=0$ for some integer $n$. Then $x-n$ is a factor of $P(x)$, and we can write $$P(x)=(x-n)Q(x)$$ for some polynomial $Q(x)$ with integer coefficients. Putting $x=0$ gives $$-nQ(0)=P(0)$$ so $n$ must be odd because $P(0)$ is odd. And putting $x=1$ gives $$(1-n)Q(1)=P(1)$$ so $n-1$ must be odd because $P(1)$ is odd. Contradiction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .