# Test for an Integer Solution

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.

-
In general, for a polynomial to have an integer root, it must have an integer root modulo $n$ for all integers $n>1$. This problem has the special case of $n=2$. –  Thomas Andrews Aug 14 '12 at 20:46
add comment

## 2 Answers

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, e.g. the Gaussian integers $\rm\: a + b\,{\it i}\$ for integers $\rm\:a,b.\:$ For much further discussion see this post and also these related posts.

-
Nice and thanks. –  Andrew Aug 14 '12 at 21:34
So you could have a similar criterion using mod 3: suppose p(-1), p(0), p(1) are not divisible by 3 then p does not have an integer root. –  i. m. soloveichik Aug 15 '12 at 0:54
Yes, it works mod $\,\rm m\,$ for any $\rm\,m\ge 2.\:$ It's a simple example of modular problem solving - looking at "simpler" structure-preserving images of problems. It's the algebraists way to "divide and conquer". For another example of the power of parity $\rm(m = 2)$ see this question. Here one quickly shows that a matrix is invertible since it has odd (so nonzero) determinant. That this simple answer got 54 votes seems to indicate how little known is the wide applicability of modular reduction, even in the case of simple parity arguments. –  Bill Dubuque Aug 15 '12 at 1:08
@i.m.soloveichik These ideas will come to the fore if you study abstract algebra. There the structure-preserving maps are known as homomorphisms and the simpler images are known as quotient objects, e.g. modular / congruence arithmetic is a special case of a quotient ring (a.k.a. residue or factor ring). –  Bill Dubuque Aug 15 '12 at 3:08
add comment

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?

-
add comment