Iranian Mathematical Olympiad

We shall prove a more general statement. That is, we prove that $x_n$ is a-periodic modulo $m$, for each $m$. In doing so, we need the following lemmas.

Lemma 1. Let $m \ge 3$ be an integer which is not a power of 2. Let $x_1$ be a fixed positive integer and $y_n$ be a sequence of positive integers such that $x_{n+1} = x_n^{y_n} + 1$, $n = 1, \dots$. If the sequence $x_n$ is eventually periodic mod $m$ then there are positive integers $b, d, T$ where $2 \le d \le m-1$ such that $y_{b+kT}, k = 0, 1, \dots$ is periodic mod $d$.

Proof. Since $m$ is not a power of two it would have an odd prime divisor, say $p$. Since the sequence $x_n \pmod m$ is eventually periodic it follows that $x_n \pmod p$ is also eventually periodic. Hence, for all large $n$, $x_{n+T} - x_n$ is divisible by $p$. Fix $b$, large enough such that $a \equiv x_b \pmod p$ and $a \ne 0, 1$. Since $p \ge 3$, such a $b$ exists because each $0 \pmod p$ followed by $1$ which is followed by $2$. Clearly $x_{b+kT} \equiv a \pmod p$ for each $a \ge 0$. Notice that $p$ divides $a^{y_{b+kT}} - a^{y_b}$. Hence, $|y_{b+kT} - y_b|$ is divisible by the order of $a$ mod $p$, namely $d$. That is, $y_{b+kT} \pmod d$ is periodic. As desired.

Now, we shall prove a nice fact about the periodicity of $S(b + kT)$, $k = 0, \dots$

Lemma 2. Let $b, T, d$ be positive integers, if the sequence $S(b + kT)$, $k = 0, \dots$ is constant mod $d$ then $d$ divides $T$ and $d \in \{1, 3, 9\}$.

Proof. Letting $k = 10^r s$ for some large enough $r$ it follows that $S(b+10^r sT) = S(b) + S(sT) \equiv S(b) \pmod d$. Whence, $S(sT) \equiv 0 \pmod d$. We can also assume $\gcd(10, T) = 1$ indeed, if $T = 2^\alpha 5^\beta T_1$, $\gcd(T_1, 10) = 1$ then, by a suitable choice of $s$ we can make power of 10.

Then, there are $s_0, s_1$ such that
$$Ts_0 \equiv 1 \pmod{100}$$

and
$$T s_1 \equiv 9 \pmod{10^{r+1}}.$$
Further, by a suitable choice of $r$ we can ensure that $T s_0 < 10^r$. It follows that
$$S((s_0 + s_1)T) = S(s_0T) + S(s_1T) - 9.$$
Since $d$ divides $S(s_0T)$, $S(s_1T)$, $S((s_0+s_1)T)$ it follows that $d$ divides 9. That is, $S((s_0+s_1)T)$. And since $S(sT) \equiv sT \pmod{9}$ it follows that $sT \equiv 0 \pmod{d}$, Hence, $d$ divides $T$. This completes our proof.

Back to our problem. We shall firstly prove that $m$ has no odd prime divisor. Assume the sequence is periodic with the minimal period of $T$. Since there are infinitely many $i$ such that $S(i)$ is divisible by $p-1$ if $p$ divides $x_i$ then $x_{i+2} \equiv 2 \pmod{p}$. If $p$ doesn't divide $x_i$ then $x_{i+1} \equiv 2 \pmod{p}$. Hence, $2$ is among the residues of $x_n$ modulo $p$. Take $a=2$ in the first lemma. It follows that the sequence $S(kT+i)$ is constant modulo the order of 2 modulo $p$, namely $d$. Hence, $d$ divides 9. That is, $p$ divides $2^9-1=7 \times 73$. If $p=7$ then for $i \equiv 0 \pmod{3}$ we have $x_{i+1} \equiv 2 \pmod{7}$ and $x_{i+2} \equiv 3 \pmod{7}$ since the order of 3 mod 7 is 6 we reached to a contradiction. The same holds for the case $i \equiv 1 \pmod{3}$. Finally, for $i \equiv 2 \pmod{3}$ we have $x_{i+1} \equiv 5 \pmod{7}$ and since the order of 5 modulo 7 is 6 we again reached to a contradiction.

If $p=73$ the numbers with orders that dividing 9 are
$$1, 2, 4, 8, 16, 32, 64, 55, 37,$$
surprisingly powers of 2. If $i$ is divisible by 9 then $x_{i+1} \equiv 2 \pmod{73}$ and $x_{i+2} \equiv 3 \pmod{73}$ while the order of 3 modulo 73 doesn't divide 9. If $i$ is not divisible by 9 then $x_{i+1}$ is not congruent to a power of 2 mod 73. Hence, its order modulo 73 doesn't divide 9.

Finally, for powers of 2 we prove that the only solutions are $m=1, 2, 4$. Let $m=2^c$ we claim that the period is of the form $1, 2, 1, 2, \dots$. Indeed if $x_i$ is odd then since the order of $x_i$ modulo $2^c$ is a power of two and for sake of periodicity it must divide 9 we would obtain that $x_i \equiv 1 \pmod{2^c}$. Hence, $x_{i+1} \equiv 2 \pmod{2^c}$ and by the same argument $x_{i+2k} \equiv 2^{S(i-1+2k)}+1 \equiv 1 \pmod{2^c}$ yielding $S(i-1+2k) \ge c$ for all $k$. Thus, $c \le \min S(i-1+2k) = 2$. Whence, $m=1, 2, 4$. ■