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
Answer: f(n) is smallest integer N such that n divides N! and f(1000000) = 25.
Put pN(x) = x(x + 1)(x + 2) ... (x + N - 1). Note first that pN(m) / N! = (m + N - 1)! / ( (m - 1)! N! ) which is a binomial coefficient and hence integral, so pN(m) is certainly divisible by N! for all positive integers m. If m = 0, -1, ... , -(N - 1), then pN(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 pN(m) = (-1)N pN(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 pN(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) = pM(x) + a1pM-1(x) + ... + aM-1p1(x) + aM, where M is the degree of M and ai are integers (just choose successively, a1 to match the coefficient of xM-1, then a2 to match the coefficient of xM-2 and so on).
Taking x = n, we conclude that n must divide aM, so there is another polynomial of the same degree, namely p(x) - aM with the same property. In other words, we may take aM = 0. Now take x = n - 1. Then p2(x), p3(x), ... are all divisible by n. So aM-1p1(n - 1) must also be divisible by n. But n and n - 1 are relatively prime, so aM-1 must be divisible by n. Hence the polynomial pM(x) + a1pM-1(x) + ... + aM-2p2(x) has the same property.
This argument continues on until we conclude that pM(x) has the same property, but a little care is needed, because in general n and pi(n - i ) are not relatively prime. However, their greatest common divisor is also the gcd of n and i! (just multiply out pi(n - i) = (n - 1)(n - 2)...(n - i ) - all terms except the i! term have a factor n). But i! divides pi(m) for all m (proved above), so the fact than n divides aM-ipi(n - i ) allows us to conclude that n divides aM-ipi(m) for all m and hence that we can drop the term.
So we have finally that pM(x) also has the property. In particular, n must divide pM(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(2656). Evidently 25 is the smallest N such that 56 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 212 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 ΔMp(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! .
© John Scholes
jscholes@kalva.demon.co.uk
18 Aug 2001