### 13th Putnam 1953

Problem B2

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

Solution

Note that n! is best possible, because 1/n! x(x + 1) ... (x + n - 1) is always integral for integral x (it is the binomial coefficient (x+n-1)Cn ).

We need a standard result from the calculus of differences. Let Δf(x) = f(x + 1) - f(x). Then p(x) = p(0) + Δ1x + 1/2! Δ2 x(x - 1) + 1/3! Δ3 x(x - 1)(x - 2) + ... + 1/n! Δn x(x - 1) ... (x - n + 1) (*), where Δm = Δmp(0) (thus Δ1 = p(1) - p(0), Δ2 = p(2) - 2p(1) + p(0) etc).

Assume this is true. Then if p(x) is integral for all integral x, all the Δm must be integral. So the result above gives n! p(x) = an integral combination of integral polynomials. Hence all the coefficients of n! p(x) are integral.

To prove the result, notice first that if f(x) = x(x - 1)(x - 2) ... (x - m + 1), then Δrf(0) = m! for r = m and 0 otherwise. So if we call the rhs of (*) q(x) , then Δmq(0) is a sum of terms which are all zero except for Δm(1/m! Δm x(x - 1) ... (x - m + 1) )(0) = Δm. Hence Δmp(0) = Δmq(0) for m = 1, 2, ... , n. Also p(0) = q(0), so by a simple induction p(m) = q(m) for m = 0, 1, 2, ... , n. But q(x) is a polynomial of degree at most n. If polyomials of degree at most n agree at n+1 points, then they must be identical. Hence p(x) = q(x).