p is prime. q(x) is a polynomial with integer coefficients such that q(k) = 0 or 1 mod p for every positive integer k, and q(0) = 0, q(1) = 1. Show that the degree of q(x) is at least p-1.
Solution
If p=2, then since q(0) ≠ q(1), q is not constant, so its degree is at least 2-1. So assume p is an odd prime. We show first that ∑k=1p-1 kn = 0 mod p for n=1,2, ..., p-2. Note that 0, s, 2s, 3s, ... , (p-1)s is an complete set of residues for any s ≠ 0 mod p, so sk(1k + 2k + ... + (p-1)k) = sk + (2s)k + ... + ((p-1)s)k = (1k + 2k + ... + (p-1)k) mod k. The congruence xk=1 mod p is not satisfied by x=0 so it can have at most k < p-1 solutions, so we can find s such that sk - 1 ≠ 0 mod p. Hence (1k + 2k + ... + (p-1)k) = 0 mod p as required.
But now if q(x) has degree ≤ p-2, then grouping the terms in xk we get q(1) + q(2) + ... + q(p-2) = 0 mod p. Contradiction since 0 < q(1) + ... + q(p-2) < p-1.
Thanks to Kamil Duszenko
© John Scholes
jscholes@kalva.demon.co.uk
2 Dec 2003
Last corrected/updated 2 Dec 2003