62nd Putnam 2001 Problem A5 Find all solutions to x n+1 - (x + 1) n = 2001 in positive integers x, n. Solution
: x = 13, n = 2: 13 3 - 14 2 = 2001. Use congruences. Note that 2002 = 2·7·11·13. Taking the equation mod x gives that 0 - 1 = 2001 (mod x), so x must be a divisor of 2002. x cannot be a multiple of 3, because then we would have 0 - 1 = 0 (mod 3). Similarly, it cannot be = 2 (mod 3). So it must be = 1 (mod 3) and n must be even. Taking the equation mod x+1 gives (-1) odd = 2001 (mod x+1), so x + 1 must divide 2002. Hence x = 1 or 13. x = 1 is obviously not a solution, so the only possibility is x = 13 and we must find all solutions to 13 n+1 - 14 n = 2001. There are obviously at most two solutions (since 13 n+1 - 14 n increases to a maximum, then decreases). It is also obvious that n = 2 is a solution. But it is not immediately obvious that there is not a second solution. The trick is to work mod 8. We then have (4 + 1) odd - (-2) even = 1. If the even is greater than 2, then 2 even = 0 (mod 8) and we have a contradiction, because expanding (4 + 1) odd we get zero terms + odd x 4 + 1 = 5 (mod 8). So the only possibility is n = 2. 62nd Putnam 2001 © John Scholes jscholes@kalva.demon.co.uk 16 Dec 2001