p(x) is a polynomial with integer coefficients. For some positive integer c, none of p(1), p(2), ... , p(c) are divisible by c. Prove that p(b) is not zero for any integer b.
Suppose p(b) = 0. Then p(x) = (x - b)q(x), where q is a polynomial with integer coefficients. Put b = cd + r, where 1 ≤ r ≤ c (note that this is different from the conventional 0 ≤ r < c, but still possible because 1, 2, ... c are a complete set of residues mod c). Then p(r) = p(b - cd) = - cd q(r) which is divisible by c. Contradiction.
3rd Putnam 1940
© John Scholes
14 Sep 1999