4
$\begingroup$

Given positive integers $a,m$, let $a_1=a,\ a_{n+1}=a^{a_n}, \forall n\in\mathbb Z_{\ge 1}$. Show that the sequence $(a_n)$ eventually becomes constant $\pmod m$.

A solution given is as follows:

Suppose that there is a counterexample. Then there is a counterexample for which $ m$ is minimal. Trivially, $ m\neq 1$.

Note that the sequence $ \{ a^j\}_{j=0}^{\infty}$ eventually becomes periodic $\pmod m$; let the length of this period be $ k$. Evidently, $ 1 \le k \le m-1$. Since $ \{a_j\}_{j=2}^{\infty} = \{ a^{a_j}\}_{j=1}^{\infty} $ does not become constant mod $ m$, it follows that $ \{a_j \}_{j=1}^{\infty}$ does not become constant mod $ k$. Thus $ k$ is a smaller counterexample than $ m$. Contradiction.

I do not understand how the bold part follows. Can someone help?

$\endgroup$
1
  • 1
    $\begingroup$ I gave a proof of the same fact here - maybe it will help you. The last paragraph in particular seems to mirror what you have here. $\endgroup$ Commented Feb 22, 2015 at 22:20

1 Answer 1

1
$\begingroup$

The proof is noticing that the value of $a^{j}\pmod n$ is determined by knowing $j\pmod k$. This means that if $a_j$ is eventually constant mod $k$, then it follows that $a_{j+1}$ is eventually constant mod $n$, because its value, $a^{a_j}$ is determined by knowing $a_j$ mod $k$. The contrapositive of this is that if $a_j$ is not constant mod $n$, it cannot be constant mod $k$ either.

$\endgroup$
1
  • $\begingroup$ Really nice explanation, thank you very much. I now get it. $\endgroup$
    – greekjoy
    Commented Feb 22, 2015 at 22:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .