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(\mathrm{mod}m)$ is eventually periodic it follows that $x_n(\mathrm{mod}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(\mathrm{mod}p)$ and $a\ne 0,1$. Since $p\ge 3$, such a $b$ exists because each $0(\mathrm{mod}p)$ followed by $1$ which is followed by $2$. Clearly $x_{b+kT}\equiv a(\mathrm{mod}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}(\mathrm{mod}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)(\mathrm{mod}d)$. Whence, $S(sT)\equiv 0(\mathrm{mod}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 $$T{s}_0\equiv 1(\mathrm{mod}100)$$

and $$T{s}_1\equiv 9(\mathrm{mod}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_{0}T)+S(s_{1}T)-9.$$ Since $d$ divides $S(s_{0}T)$, $S(s_{1}T)$, $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(\mathrm{mod}9)$ it follows that $sT\equiv 0(\mathrm{mod}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(\mathrm{mod}p)$. If $p$ doesn't divide $x_i$ then $x_{i+1}\equiv 2(\mathrm{mod}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(\mathrm{mod}3)$ we have $x_{i+1}\equiv 2(\mathrm{mod}7)$ and $x_{i+2}\equiv 3(\mathrm{mod}7)$ since the order of 3 mod 7 is 6 we reached to a contradiction. The same holds for the case $i\equiv 1(\mathrm{mod}3)$. Finally, for $i\equiv 2(\mathrm{mod}3)$ we have $x_{i+1}\equiv 5(\mathrm{mod}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(\mathrm{mod}73)$ and $x_{i+2}\equiv 3(\mathrm{mod}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(\mathrm{mod}{2}^c)$. Hence, $x_{i+1}\equiv 2(\mathrm{mod}{2}^c)$ and by the same argument $x_{i+2k}\equiv 2^{S(i-1+2k)}+1\equiv 1(\mathrm{mod}{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$. ■