Question: This came up an a training piece for the Putnam Competition and also in Ireland and Rosen.

The question posed was basically:

Let $p(x)$ be a polynomial with integer coefficients satisfying that $p(0)$ and $p(1)$ are odd. Show that $p$ has no integer zeros.

I&R give an example:

$p(x) = x^2 - 117x + 31$ and show (no problem) that for any $n$ whether even or odd, $p(n)$ will be odd. And claim that this shows $p(n)$ will never be $0$.

I can see, e.g., that $x^2 + 2x + 1$ will be odd substituting an even $n$ and even for an odd $n$. 

But would appreciate help in understanding the underlying math and what is happening here.

Also, as a second part, can a general statement about the existence of an integer solution be made if $n$, even and odd, generates an even and an odd as in the last example.

I can see that if you look at these equations (mod $2$), you can distinguish whether there is an integer solution. And I would guess this is intimately connected with the question.

Thanks as always.

Answer: 
**Hint** $\ $ If an integer coefficient polynomial has an integer root $\rm\,n,\,$ i.e.$\rm\ p(n) = 0,\ $ then $\rm\,n\,$ remains a root modulo $2$, i.e. $\rm\ p(n)\equiv 0\,\ (mod\ 2).\:$ So, contrapositively, if a polynomial has no roots modulo $2$ then it has no integer roots. This leads to the following simple 

**Parity Root Test** $\ $ A polynomial $\rm\:P(x)\:$ with integer coefficients 
has no integer roots if its constant coefficient and coefficient sum are both odd. 

**Proof** $\ $ The test verifies that $\rm\ P(0) \equiv 1\equiv P(1)\ \ (mod\ 2)\:,\ $ i.e. 
that $\rm\:P(x)\:$ has no roots modulo $2$, hence no integer roots. $\ $ **QED** 

E.g. $\rm\:\ a\ X^2 + b\ X + c\ $ has no integer roots 
if $\rm\:c\:$ is odd and $\rm\:a,\:b\:$ have equal parity $\rm\:a\equiv b\ (mod\ 2)$

The Parity Root Test generalizes to any [ring with a sense of parity,](https://math.stackexchange.com/a/26843/242) e.g. the Gaussian integers $\rm\: a + b\,{\it i}\ $ for integers $\rm\:a,b.\:$ For much further discussion see [this post](https://math.stackexchange.com/a/15670/242) and also these [related posts.](https://math.stackexchange.com/search?q=user%3A242+%22parity+root+test%22)
The mod $2$ thing is easiest. Here is another idea.

Note that the polynomial expression $f(x)-f(y)$ is divisible by $x-y$ because $x^r-y^r=(x-y)(x^{r-1}+x^{r-2}y+\dots + xy^{r-2}+y^{r-1})$ and the polynomial is built up from such expressions.

So $f(n)-f(0)$ is divisible by $n$, and $f(n)-f(1)$ is divisible by $n-1$. Whence $-1$ is divisible by both $n$ and $n-1$ and you can complete the argument in various ways.

I mention the method because it can be used to answer questions about $n$ in other circumstances. For example, if you are given/have $f(7)=3$ and you want $f(n)=0$ you have $(n-7)|3$ so that $n=4, 6, 8, 10$ are the only possibilities.