Putnam 1997, Problem B-5

Prove that for $n \geq 2$,
$$\underbrace{2^{2^{\cdot^{\cdot^{2}}}}}_{n \text{ terms}} \equiv \underbrace{2^{2^{\cdot^{\cdot^{2}}}}}_{n-1 \text{ terms}} \pmod{n}.$$

Solution:
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 \pmod{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 \). (Thanks to Anoop Kulkarni for catching a lethal typo in an earlier version.)