IMO 1999 Problem B1 Find all pairs (n, p) of positive integers, such that: p is prime; n ≤ 2p; and (p - 1) n + 1 is divisible by n p-1 .
(1, p) for any prime p; (2, 2); (3, 3). Solution by Gerhard Woeginger, Technical University, Graz : (1, p) for any prime p; (2, 2); (3, 3). Evidently (1, p) is a solution for every prime p. Assume n > 1 and take q to be the smallest prime divisor of n. We show first that q = p. Let x be the smallest positive integer for which (p - 1) x = - 1 (mod q), and y the smallest positive integer for which (p - 1) y = 1 (mod q). Certainly y exists and indeed y  3. We show that there are no solutions of this type. Expand (p - 1) p + 1 by the binomial theorem, to get (since (-1) p = -1): 1 + -1 + p 2 - 1/2 p(p - 1)p 2 + p(p - 1)(p - 2)/6 p 3 - ... The terms of the form (bin coeff) p i with i >= 3 are obviously divisible by p 3 , since the binomial coefficients are all integral. Hence the sum is p 2 + a multiple of p 3 . So the sum is not divisible by p 3 . But for p > 3, p p-1 is divisible by p 3 , so it cannot divide (p - 1) p + 1, and there are no more solutions. 40th IMO 1999 © John Scholes jscholes@kalva.demon.co.uk 7 Sep 1999 Last corrected/updated 19 Aug 03