Solution to puzzle 49: An odd polynomial

Let p(x) = a₀ + a₁x + ... + a_nxⁿ.
Then p(0) = a₀ is odd, and p(1) = a₀ + ... + a_n is odd.

We now use the polynomial remainder theorem, which implies that, for unequal integers a and b, (b − a) divides (p(b) − p(a)). A short proof follows.

We have p(b) − p(a) = a₁(b − a) + a₂(b² − a²) + ... + a_n(bⁿ − aⁿ).
For n > 1, bⁿ − aⁿ = (b − a)(bⁿ⁻¹ + abⁿ⁻² + ... + aⁿ⁻²b + aⁿ⁻¹).
Therefore, for n > 0, b − a divides bⁿ − aⁿ, and so b − a divides p(b) − p(a).

By the polynomial remainder theorem, 2 divides p(k+2) − p(k), for any integer, k.
Since p(0) is odd, p(k) is odd, for all even k. (The sum of an odd number and an even number is odd.)
Similarly, since p(1) is odd, p(k) is odd, for all odd k.
Hence p(k) is odd for all integers.

Therefore p has no integer roots.

A proof by induction

We can also show that p(k) is odd, for any integer, k, using mathematical induction.

If k is even, then trivially a₁k + ... + a_nkⁿ is even, and therefore p(k) is odd.

For odd k, we use induction on the degree of the polynomial.

The basis cases are:
Degree 0: p(k) = a₀. This is true by definition, as a₀ is odd.
Degree 1: p(k) = a₀ + a₁k. Since a₀ is odd, and a₀ + a₁ is odd, a₁ is even. Hence a₀ + a₁k is odd.

For the induction step, we assume the inductive hypothesis: p(k) is odd if the degree of p is less than n.

Consider p(k) = a₀ + k(a₁ + ... + a_nkⁿ⁻¹), where n 2.
If a₁ is even, p(k) = (a₀ + k) + k(a₁−1 + ... + a_nkⁿ⁻¹).
If a₁ is odd, p(k) = (a₀ + k²) + k(a₁ + (a₂−1)k + ... + a_nkⁿ⁻¹).

In both cases, p(k) equals an even number plus an odd number (k) multiplied by an odd number (by the inductive hypothesis.)
Hence, p(k) is odd, which concludes the induction step.

It may be asked why we needed to include the proof for degree 1 in the basis step. Cannot that be proved in the induction step? It can, but not without some qualification.

In the induction step, we must handle the case where n = 1 and a₁ is odd. Without special provision, we would have p(k) = (a₀ + k²) + k(a₁ − k), where a₁ − k is of degree 1, and hence not within the inductive hypothesis. The special provision can take the form either of noting that, if n = 1, a₁ must be even; or of transferring the case n = 1 to the basis step.

The Mystery Polynomial

What little is known about the Mystery Polynomial can be summarised as follows:

All of its coefficients are integers.
Its constant term is 1492.
The sum of the coefficients of its even exponents (including the constant term) is 1776.
The sum of the coefficients of its odd exponents is 1621.

Does the Mystery Polynomial have any integer roots?

Source: Original