MHB What is the solution to Problem B-5 in the 1997 Putnam Competition?

[Ackbach]

Here is this week's POTW:

-----

Prove that for $n\geq 2$,
\[
\overbrace{2^{2^{\cdots^{2}}}}^{\mbox{$n$ terms}} \equiv
\overbrace{2^{2^{\cdots^{2}}}}^{\mbox{$n-1$ terms}} \quad \pmod{n}.
\]

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 236 - Oct 06, 2016

This was Problem B-5 in the 1997 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

Define the sequence $x_1 = 2$, $x_n = 2^{x_{n-1}}$ for $n > 1$. It suffices to show that for every $n$, $x_m \equiv x_{m+1} \equiv \cdots \pmod n$ for some $m < n.$ We do this by induction on $n$, with $n=2$ being obvious.

Write $n = 2^a b$, where $b$ is odd. It suffices to show that $x_m \equiv \cdots$ modulo $2^a$ and modulo $b$, for some $m < n$. For the former, we only need $x_{n-1} \geq a$, but clearly $x_{n-1} \geq n$ by induction on $n$. For the latter, note that $x_m \equiv x_{m+1} \equiv \cdots\pmod b$ as long as $x_{m-1} \equiv x_m \equiv \cdots \pmod{\phi(b)}$, where $\phi(n)$ is the Euler totient function. By hypothesis, this occurs for some $m < \phi(b) + 1 \leq n$.