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: 
We know

$$f(0) \equiv 1 \pmod{2}$$

This means that the constant term of $f$ is an odd integer.

---

We also know 

$$f(1) \equiv 1 \pmod{2}$$

This means that the sum of the coefficients of $f$ is odd.

---

Consider $f(x)$ for a general $x \in \mathbb{Z}$. 

**Case 1**: $x$ is even.

If $x$ is even, all of the powers of $x$ must also be even, and since the product of even numbers with any integer coefficients is also even, everything but the constant term of $f$ is even. Thus, $f(x)$ must be odd. 

**Case 2**: $x$ is odd.

If $x$ is odd, all of the powers of $x$ must also be odd. We have a bunch of odd numbers $x^i$ (including $x^0)$, and we are adding multiples of them together. We know that the *sum* of the coefficients is odd; this means we have, in total, an *odd* number of $x^i$s. The sum of an odd number of odd numbers must be odd, and so $f(x)$ is odd. 

---

We've proven that $f(x)$ is odd for integer $x$. It follows, *a fortiori*, that $f(x)$ is nonzero.
If you plug an integer into a polynomial and this equals zero, then you can look at the entire computation mod your favorite $n$. In this case, try two. What does the equation look like then?