Putnam 2001 A5, part 2

When we left off, we had seen that $(a,n) = (13,2)$ solved the equation $a^{n+1} - (a+1)^n = 2001$, and any other positive integer solution pair had to be of the form $(7,2k+1)$ or $(13,2k)$ for some positive integer $k$. It remains to rule out all of the rest of these.

But wait! Let's look mod $3$; since both of our $a$'s reduce to $1$ mod $3$, we get $1-2^n \equiv 0$ mod $3$, which happens if and only if $n$ is even. So $(7,2k+1)$ doesn't work for any $k$.

It seems like we won't be able to do the last part, ruling out all the other $(13,2k)$, using congruence conditions only, because using congruence conditions usually either rules out all solutions or doesn't rule out infinitely many, and we already know there's at least one solution. (SPOILER ALERT: it's easy if you know the right congruence! To avoid the following discussion, try looking mod 8. The official Putnam solutions page doesn't miss any tricks.)

Well, how about bounding the possible values of $n$ when $a=13$? Does $13^{n+1} - 14^n$ grow without bound? Let's see: if we tried to compare $13^{n+1} > 14^n$, this would reduce to $13 > (1 + 1/13)^n$. Huh, it looks like for large enough $n$, the $14^n$ term actually gets bigger than the $13^{n+1}$ term, so the left side is negative.

How large is large enough? Well, the expansion of $(1+1/13)^n$ starts off $1 + n/13 + \cdots$, and all the other terms are positive, so if $n \ge 156$ then the left side of the original equation is negative. So we just need to rule out all $n < 156$.

This can be done using congruence conditions. Let's just mash together as many congruences as we can. So:

Mod $5$: $3^{n+1} - 4^n \equiv 1$, write out powers of $3$ $\Rightarrow$ $n \equiv 2$ mod $4$

Mod $23$: $13^{n+1} \equiv 14^n$; write out powers of $13$ $\Rightarrow$ $n \equiv 2$ mod $22$

Mod $29$: $13^{n+1} \equiv 14^n$; write out powers of $13$ $\Rightarrow$ $n \equiv 2$ mod $28$

Putting these together gives $n \equiv 2$ mod $308$, which means that if $n$ is not $2$, then it can't be less than $156$, and we're done.

As you might expect, this one was a little tougher for the contestants. I'm a little surprised at just how tough it was, though--only 31 of the top 200 got (nearly) full credit.

Top 200 scores:
(12,9,10),(9,41,119)