Putnam 2001 A5, part 1

Prove that there are unique positive integers $a, n$ such that $a^{n+1}-(a+1)^n = 2001$.

Now this is a truly enjoyable problem. Short, easy statement, interesting proof, lovely result (of course I have a fondness for Diophantine equations, so I may be a little biased here).

As with many Putnam problems, it's not obvious where to start. With many of these Diophantine equation problems, it usually helps to consider the equation mod $m$, for some carefully chosen number(s) $m$. (This is a technique that you must familiarize yourself with in order to solve many of these problems, and it's completely elementary--see e.g. http://www.math.rutgers.edu/~erowland/modulararithmetic.html for a brief introduction.)

Prime values of $m$ are usually easiest. Which primes would simplify the equation nicely? Well, one obvious start is primes dividing $2001$. So let's see which ones those would be...$2001$ is divisible by $3$, and then it may take awhile to find more factors after that (we may even start to suspect that $667$ is prime), but eventually we can get $2001 = 3 \cdot 23\cdot 29$. (After you get this by trial division, you can check by noticing that $26^2 = 676$, and $23 \cdot 29 = (26-3)(26+3) = 26^2 - 9 = 676 - 9$.) Hopefully this doesn't take too long--three hours can go by awfully quickly if we spend too much of it factoring three-digit integers!

So if we look mod 3, mod 23, or mod 29, we get $a^{n+1}-(a+1)^n \equiv 0$, and it's not immediately clear how that is going to help us. Although it's frustrating to have done all that work for what seems to be no reward, let's shelve that for the time being.

While doing that reduction, we might realize that it would be better if we could kill one of the terms on the left side. Aha--so let's try taking the equation mod $a$ instead. Notice that $a \equiv 0$ and $a+1 \equiv 1$, so the left side becomes $-1$. So we just get $-1 \equiv 2001$ mod $a$, so $a$ divides $2002$. (To see this without using modular arithmetic, just think of expanding the left side in powers of $a$; then the constant term will be $-1$ and everything else will be divisible by $a$, so if you add $1$ to both sides the left side will be divisible by $a$ and the right side will be $2002$.)

Well, that certainly narrows it down, but $2002$ has a lot of divisors. In fact, $2002 = 2 \cdot 7 \cdot 11 \cdot 13$, so it has $16$ different positive divisors. (How did I get this number without writing them all down? Exercise for the reader!)

If we wanted to kill off the other term, we could take the equation mod $a+1$. Then we get $(-1)^{n+1} \equiv 2001$ mod $a+1$, so there are two cases: $n$ is odd and $a+1$ divides $2000$, or $n$ is even and $a+1$ divides $2002$.

Hmm, so that narrows down the candidates for $a$ even more. We need a divisor $a$ of $2002$ such that $a+1$ divides $2000$ or $2002$. Looks like we're going to have to write down all the divisors of $2002$. If you did the parenthetical exercise above, you should have some idea of how to write them all down systematically, so let's cut to the chase here: \[a = 1, 2, 7, 11, 13, 14, 22, 26, 77, 91, 143, 154, 182, 286, 1001, 2002. \] Phew!

So which of these have the property that $a+1$ is a divisor of $2000$ or $2002$? It turns out that only $a=1, 7, 13$ have this property (you do have to go through and check each of these separately, but each check is very quick). And we can throw out $a=1$ right away: $1^{n+1}-2^n = 1-2^n$ can't equal $2001$ for any positive integer $n$, since it's definitely negative. All right, that's real progress! We've shown that if $a, n$ satisfy the conditions of the problem, then $a=7$ (and $n$ is odd) or $a=13$ (and $n$ is even).

We might start to wonder now what the solution is. It can't hurt to try small values of $n$ for each of our $a$'s; this will also give us a bit of a sense of how big the left side gets. Well, notice that $13^3$ is about $2000$. In fact, if we try $n=2$, we can see that $13^3-14^2 = 2197-196 = 2001$. Voila--there is our solution, and now all we have to do is show that it's unique.

Continued in the next post.