1991 USAMO Problems/Problem 3

From AoPSWiki

Problem

Show that, for any fixed integer $\,n \geq 1,\,$ the sequence $2, \; 2^2, \; 2^{2^2}, \; 2^{2^{2^2}}, \ldots \pmod{n}$ is eventually constant.

[The tower of exponents is defined by $a_1 = 2, \; a_{i+1} = 2^{a_i}$ . Also $a_i \pmod{n}$ means the remainder which results from dividing $\,a_i\,$ by $\,n$ .]

Solution

Suppose that the problem statement is false for some integer $n \ge 1$ . Then there is a least $n$ , which we call $b$ , for which the statement is false.

Since all integers are equivalent mod 1, $b\neq 1$ .

Note that for all integers $b$ , the sequence $2^0, 2^1, 2^2, \dotsc$ is eventually becomes cyclic mod $b$ . Let $k$ be the period of this cycle. Since there are $k-1$ nonzero residues mod $b$ . $1 \le k\le b-1 < b$ . Since $2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \dotsc$ does not become constant mod $a$ , it follows the sequence of exponents of these terms, i.e., the sequence $1, 2, 2^2, 2^{2^{2}}, \dotsc$ does not become constant mod $k$ . Then the problem statement is false for $n=k$ . Since $k<b$ , this is a contradiction. Therefore the problem statement is true. $\blacksquare$