# If $P(0)$ and $P(1)$ are both odd, show that $P(x)$ has no integer roots

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?

• Easier: We have $P(a+bn)\equiv P(a)\pmod{n}$ for all $a,b\in\mathbb{Z}$. This also proves your generalised result. Commented Sep 12, 2021 at 6:05
• Can you please add the year the question was asked. Commented Sep 12, 2021 at 15:25
• @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. Commented Sep 12, 2021 at 15:52

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!
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.