A Fresh Polynomial Question

Accessible for all HS grades

Let p(x) be a real polynomial of degree n such that p(m) is integral for all integers m. Show that if q is a coefficient of p(x), then n!q is an integer.

How do we approach this problem? Let’s try to digest what the problem is saying first.

What does p(m) is integral for all integers of m mean? Whenever we substitute an integer m into p(x), p(m) will always be an integer. However, does this necessarily imply that all the coefficients of the p(x) will also be integral? We see that this is not necessarily the case. Consider the following p(x) which has non-integral coefficients.

Why is the above p(x) always an integer when the x we substitute is an integer? We see that x and x+1 are adjacent integers and, therefore, one has to contain a factor of 2, meaning that p(x) will be an integer. With this following example in mind, we can construct similar p(x)’s.

x, x+1, x+2 are 3 adjacent integers. Therefore, among these three integers, there will be a multiple of 3 and at least a multiple of 2, meaning p(x) maps from integers to integers. Through these two constructions, we can see a pattern forming. However, why do these p(x)’s that we have constructed all map from integers to integers?

Perhaps writing it in this form could give a clue.

Notice that this is simply

All the p(x)’s in similar forms to what we’ve created above are simply binomial coefficients, which are all integers, and can simply be expressed in choose notation.

Thus, we can also notice that all polynomials in the form below map from integers to integers.

Now we can construct a general polynomial p(x) that maps from integers to integers. Since we are dealing with the coefficient of this polynomial, we want to find an expression for each coefficient of p(x).

Suppose that p(x) has degree n and maps from integers to integers. To uniquely pin down p(x), we need at least n+1 points to find the explicit polynomial that runs through these points.

Given n+1 pairs (x0, y0), …., (xn, yn) with all xi distinct, we want to show that p(x) with at most degree n is the unique polynomial that passes through all the points. Suppose for contradiction that there exists another polynomial q(x) where q(xi) = yi for all of the n+1 pairs of points.

Now we can consider the polynomial k(x) = p(x) - q(x). Since by assumption p(x) and q(x) are different polynomials, k(x) is a non zero polynomial with at most degree n. This implies that the polynomial k(x) has a maximum of n roots. However, k(xi) = p(xi)- q(xi) = 0 on n+1 different points since p(xi) = q(xi) for all the n+1 distant xi. Thus, we’ve reached a contradiction and p(x) is the unique polynomial of maximum degree n that goes through all n+1 points. We can now construct the n+1 points and for simplicity, we will use the points defined below.

Now we can consider a part of the polynomial we will try to construct.

The above polynomial isn’t exactly the polynomial that will go through all the above points. However, it is really close. At the very first look, it isn’t obvious how and why we’ve constructed the above expression.

However, notice that in the way that we’ve constructed the above polynomial when we substitute x = 0, the first term is equal to 1 while every other term is equal to 0 as they all contain (x-0). Thus, to ensure that our polynomial goes through the point (0, b0), we make the coefficient the first term b0.

Similarly, if we substitute 1 into p(x), the second term is equal to 1 and every other term cancels out as they all contain (x-1). Thus, to make sure that our polynomial also passes through the point (0, b1), we simply coefficient of the second term b1. Now that we spot a pattern, we can generalise this to all n+1 terms where the expression will be the following.

Now, the above polynomial that we’ve constructed is the unique polynomial that passes through all the points.

Now, all we need to show is that if we multiply every coefficient by n! we get an integer. Notice that all the denominators can be written as factorials.

In general, the denominators can be written as the above expression. Thus, to show that each of the coefficients of p(x) when multiplied by n! is an integer, all we need to show is that n! has a factor of the denominator.

The above expression once again looks similar to n choose k except multiplied with a (-1) to a certain power. Since the minus 1 doesn’t change the nature of whether the expression is an integer, the above expression is simply a positive or negative n choose k. Since n choose k is always an integer, the above expression is always an integer. Thus, we’ve proven that any of the coefficients of p(x) multiplied by n! is an integer.

The question in this article is from the following website. It also contains more challenging questions if you wish to attempt them. https://www.math.cmu.edu/~ploh/docs/math/2020-295/11-integer-poly.pdf