Q. Prove that a polynomial $f(x)$,with integer coefficients has no integral roots if $f(0)$ and $f(1)$ are both odd integers.

My attempt:



now $f(0)=a_0$ which is an odd integer. and $f(1)=(a_0+a_1+a_2+\dots+a_n$) an odd integer.

Now, what is the strategy I need to imply to prove that $f(x)$ can't have integral roots.


marked as duplicate by Adam Hughes, Empty, Jyrki Lahtonen Aug 6 '15 at 8:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Hint: If $a$ and $b$ are integers such that $a\equiv b\pmod2$, then $f(a)\equiv f(b)\pmod2$ as well. Can you prove this? $\endgroup$ – Jyrki Lahtonen Aug 6 '15 at 7:48
  • $\begingroup$ Sorry! I can't, I am novice to polynomials. :( $\endgroup$ – reego Aug 6 '15 at 7:50
  • $\begingroup$ Ok, @Heinz. Are you familiar with congruences? If not, think of it the following way instead: If $a,n,m,n>0,$ are integers can you show that $a^n$ and $(a+2m)^n$ have the same parity? In other words they are either both odd or both even. And if you are familiar with congruences can you show that $a\equiv b$ implies $a^k\equiv b^k$? $\endgroup$ – Jyrki Lahtonen Aug 6 '15 at 7:51
  • $\begingroup$ I understand the above congruence but I can't prove it. For the later I am confused how to show $(a+2m)^n$ and $a^n$ of the same parity. Should I expand $(a+2m)^n$@Jyrki Lahtonen $\endgroup$ – reego Aug 6 '15 at 8:01
  • $\begingroup$ The suggestion about parities of $a^n$ and $(a+2m)^n$ is simply a stepping stone in proving that congruence. And, yes, @Heinz, expanding $(a+2m)^n$ does show that (or induction on $n$ and the rule that $a\equiv b$ and $c\equiv d$ together imply that $ac\equiv bd$). The general plan I have in mind is that I want you to prove that for each term $a_ix^i$ of $f(x)$ you have $a_ia^i\equiv a_ib^i$ whenever $a\equiv b$. Then another induction on the number of terms (using the rule:$a\equiv b$ and $c\equiv d$ together imply that $a+c\equiv b+d$) takes you to the finish line. $\endgroup$ – Jyrki Lahtonen Aug 6 '15 at 8:08

Since $f(0)=a_0$ is odd and $f(1)=a_0+\ldots +a_n$ is odd, we have that $a_1+\ldots +a_n$ is even. Hence

$$f(2k)=a_0+2(a_1k)+2(2a_2k^2)+2(4a_3k^3)+\ldots +2(2^{n-1}k^na_n)$$

is odd for all $k$, and

$$f(2k+1)=\sum_{k=1}^na_k\sum_{i=1}^k{k\choose i}(2k)^i.$$

Since all the inner summands are even except when $i=0$ we see that


which is an even plus an odd, hence all values of $f$ are odd.

  • $\begingroup$ I am confused with $f(2k+1)=\sum_{k=1}^na_k\sum_{i=1}^k{k\choose i}(2k)^i.$. How come the series happen to be like this. Please explain. $\endgroup$ – reego Aug 6 '15 at 8:49
  • $\begingroup$ @HeinzKloube It's the binomial theorem for $(2k+1)^k$. you can write in a $1^{k-i}$ next to the $(2k)^i$ if that helps you visualize it. $\endgroup$ – Adam Hughes Aug 6 '15 at 16:19

You are almost done: $a_0$ is odd and $a_0+a_1+\cdots+a_n$ is odd imply that $a_1+\cdots+a_n$ is even.

Next, for each $x\in\mathbb{N}$, verify that $a_jx^j$ and $a_jx$ have the same parity whenever $j\geq 1$: $$ 2|a_jx\iff [(2|a_j)\text{ or }(2|x)]\iff[(2|a_j)\text{ or }(2|x^j)]\iff 2|a_jx^j. $$ Now the claim follows: for any $x\in\mathbb{N}$, $\sum_{j=0}^na_jx^j$ has the same parity as $$ \underbrace{a_0}_{\text{odd}}+(\underbrace{a_1+\cdots+a_n}_{\text{even}})x $$ which is odd. In particular, $\sum_{j=0}^na_jx^j$ cannot be zero.


The nonzero powers of an even number are even, the powers of an odd number are odd.

Then the value of $f$ for an even argument is the sum of $a_0$ and even terms so that

$$f(e)=a_0+a_1e'+a_2e''+\dots+a_ne^{(n)}$$ has the parity of $a_0=f(0)$.

And the value of $f$ for an odd argument is the sum of all coefficients times an odd factor so that

$$f(o)=a_0+a_1(e'+1)+a_2(e''+1)+\dots+a_n(e^{(n)}+1)$$ has the parity of $a_0+a_1+a_2+\cdots a_n=f(1)$.

Conclusion: for any integer, the function value is odd, thus nonzero.


Not the answer you're looking for? Browse other questions tagged or ask your own question.