Let p(x) = a_{0} + a_{1}x + ... + a_{n}x^{n}.

Then p(0) = a_{0} is odd, and p(1) = a_{0} + ... + 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_{1}(b − a) + a_{2}(b^{2} − a^{2}) + ... + a_{n}(b^{n} − a^{n}).

For n > 1, b^{n} − a^{n} = (b − a)(b^{n−1} + ab^{n−2} + ... + a^{n−2}b + a^{n−1}).

Therefore, for n > 0, b − a divides b^{n} − a^{n}, 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.

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

If k is even, then trivially a_{1}k + ... + a_{n}k^{n} 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_{0}. This is true by definition, as a_{0} is odd.

Degree 1: p(k) = a_{0} + a_{1}k. Since a_{0} is odd, and a_{0} + a_{1} is odd, a_{1} is even. Hence a_{0} + a_{1}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_{0} + k(a_{1} + ... + a_{n}k^{n−1}), where n 2.

If a_{1} is even, p(k) = (a_{0} + k) + k(a_{1}−1 + ... + a_{n}k^{n−1}).

If a_{1} is odd, p(k) = (a_{0} + k^{2}) + k(a_{1} + (a_{2}−1)k + ... + a_{n}k^{n−1}).

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_{1} is odd. Without special provision, we would have p(k) = (a_{0} + k^{2}) + k(a_{1} − k), where a_{1} − 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_{1} must be even; or of transferring the case n = 1 to the basis step.

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