### 62nd Putnam 2001

Problem A5

Find all solutions to xn+1 - (x + 1)n = 2001 in positive integers x, n.

Solution

Answer: x = 13, n = 2: 133 - 142 = 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 13n+1 - 14n = 2001.

There are obviously at most two solutions (since 13n+1 - 14n 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 2even = 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.