IMO 1997 SL 12

Origin: ITA

Problem

Let p be a prime number and let f(x) be a polynomial of degree d with integer coefficients such that: (i) f(0) = 0, f(1) = 1; (ii) for every positive integer n, the remainder of the division of f(n) by p is either 0 or 1. Prove that d \geqp −1.

Solution

Lemma. For any polynomial P of degree at most n, the following equality holds: n+1  i=0 (−1)i n + 1 i  P(i) = 0. Proof. See (SL81-13). Suppose to the contrary that the degree of f is at most p −2. Then it follows from the lemma that 0 = p−1  i=0 (−1)i p −1 i  f(i) \equiv p−1  i=0 f(i) (mod p),

since
p−1 i  = (p−1)(p−2)\cdot\cdot\cdot(p−i) i! \equiv(−1)i (mod p). But this is clearly im- possible if f(i) equals 0 or 1 modulo p and f(0) = 0, f(1) = 1. Remark. In proving the essential relation p−1 i=0 f(i) \equiv0 (mod p), it is clearly enough to show that Sk = 1k + 2k + \cdot \cdot \cdot + (p −1)k is divisible by p for every k \leqp −2. This can be shown in two other ways. (1) By induction. Assume that S0 \equiv\cdot \cdot \cdot \equivSk−1 (mod p). By the binomial formula we have 0 \equiv p−1  n=0 [(n + 1)k+1 −nk+1] \equiv(k + 1)Sk + k−1  i=0 k + 1 i  Si (mod p), and the inductive step follows. (2) Using the primitive root g modulo p. Then Sk \equiv1 + gk + \cdot \cdot \cdot + gk(p−2) = gk(p−1) −1 gk −1 \equiv0 (mod p).