35th Putnam 1974 Problem A6 Let f(n) be the degree of the lowest order polynomial p(x) with integer coefficients and leading coefficient 1, such that n divides p(m) for all integral m. Describe f(n). Evaluate f(1000000). Solution
: f(n) is smallest integer N such that n divides N! and f(1000000) = 25. Put p N (x) = x(x + 1)(x + 2) ... (x + N - 1). Note first that p N (m) / N! = (m + N - 1)! / ( (m - 1)! N! ) which is a binomial coefficient and hence integral, so p N (m) is certainly divisible by N! for all positive integers m. If m = 0, -1, ... , -(N - 1), then p N (m) is zero, which can also be regarded as a multiple of N!. If m < -(N - 1), then we may put m = -m' - (N - 1) where m' is positive. Then p N (m) = (-1) N p N (m') which is divisible by N!. So certainly if we take N to be the smallest integer such that n divides N!, then we can find a polynomial with leading coefficient 1 (namely p N (x) ) such that n divides p(m) for all integral m. Now suppose p(x) is any polynomial with this property. We may write p(x) = p M (x) + a 1 p M-1 (x) + ... + a M-1 p 1 (x) + a M , where M is the degree of M and a i are integers (just choose successively, a 1 to match the coefficient of x M-1 , then a 2 to match the coefficient of x M-2 and so on). Taking x = n, we conclude that n must divide a M , so there is another polynomial of the same degree, namely p(x) - a M with the same property. In other words, we may take a M = 0. Now take x = n - 1. Then p 2 (x), p 3 (x), ... are all divisible by n. So a M-1 p 1 (n - 1) must also be divisible by n. But n and n - 1 are relatively prime, so a M-1 must be divisible by n. Hence the polynomial p M (x) + a 1 p M-1 (x) + ... + a M-2 p 2 (x) has the same property. This argument continues on until we conclude that p M (x) has the same property, but a little care is needed, because in general n and p i (n - i ) are not relatively prime. However, their greatest common divisor is also the gcd of n and i! (just multiply out p i (n - i) = (n - 1)(n - 2)...(n - i ) - all terms except the i! term have a factor n). But i! divides p i (m) for all m (proved above), so the fact than n divides a M-i p i (n - i ) allows us to conclude that n divides a M-i p i (m) for all m and hence that we can drop the term. So we have finally that p M (x) also has the property. In particular, n must divide p M (1) = M! so M must be at least as big as N, the smallest number with this property. That establishes that f(n) is just the smallest N such that n divides N!. Finally we want f(1000000) = f(2 6 5 6 ). Evidently 25 is the smallest N such that 5 6 divides N! (25! includes 5 x 10 x 15 x 20 x 25 which is just the 6 powers of 5 needed). Certainly at least 2 12 divides 25! (which includes 12 even numbers in the product: 2, 4, 6, ... , 24), so f(1000000) = 25. Comment. The middle section of this argument, where we show that n must divide M! is rather clumsy. One could tidy it up as follows. For any polynomial q(x) of degree m, define Δq(x) = q(x) - q(x-1). It has degree m - 1 and leading coefficient m times that of q. Hence if p(x) has degree M and leading coefficient 1, then Δ M p(x) is simply the constant polynomial M!. But it is also a linear combination of polynomials p(x - m) for various m. Hence n divides M! . 35th Putnam 1974 © John Scholes jscholes@kalva.demon.co.uk 18 Aug 2001