Problem of the Fortnight #11

Suppose p(x) is a polynomial with integer coefficients such that the sum of its coefficients is an odd integer, and that its constant coefficient is also odd. Can the polynomial have an integer root?

Solution by Dave Stone:

It cannot.  First observe that the oddness or evenness of the sum of a set of integers depends on whether there are a odd or even number of odd numbers in the set.  An odd number of odd numbers produces an odd sum; an even number of odd numbers produces an even sum.

Next, let us assume we have a P(x) of degree n satisfying the above conditions with an integer solution.

That is, Ax^n + Bx^n-1 . . . . + Z = 0

We know that A + B +. . . + Z is odd, and that Z is odd, AND that an odd number of the constants A through Z are odd.

Move Z to the other side, and factor out x, giving

x (Ax^n-1 + Bx^n-2 + . . . + Y) = -Z

The right side of the equation is odd, so the left hand side must be odd as well.  Integer x must then be odd, and so must our new polynomial of degree n-1.  Since x is odd, all x powers in the polynomial must be odd.

So A*oddnumber + B*oddnumber + . . . + Y must be odd.  That means that an ODD number of the constants A through Y must be odd.  However, we already knew that an ODD number of the constants A through Z were odd, and we removed an odd constant Z, meaning that there must now be an EVEN number of odd constants in A through Y.   Contradiction.  So there cannot be a polynomial with integer solution satisfying the conditions.