Let \(a > 1\) be a positive integer and \(d > 1\) be a positive integer coprime to \(a\). Let \(x_1=1\), and for \(k\geq 1\), define
\[x_{k+1} = \begin{cases} x_k + d &\text{if } a \text{ does not divide } x_k \\ x_k/a & \text{if } a \text{ divides } x_k \end{cases}\]
Find, in terms of \(a\) and \(d\), the greatest positive integer \(n\) for which there exists an index \(k\) such that \(x_k\) is divisible by \(a^n\).Answer: \(n\) is the exponent with \(d<a^{n}<a d\).
By trivial induction, \(x_{k}\) is coprime to \(d\).
By induction and the fact that there can be at most \(a-1\) consecutive increasing terms in the sequence, it also holds that \(x_{k}<d a\) if \(x_{k}=x_{k-1}+d\) and that \(x_{k}<d\) if \(x_{k}=\frac{x_{k-1}}{a}\) or \(k=1\). This gives the upper bound on the exponent.
This implies that the sequence is (eventually) periodic, and that both increasing and decreasing steps happen infinitely many times. Let \(a^{-k}\) be the multiplicative inverse of \(a^{k}\) modulo \(d\). The sequence contains elements congruent to \(1, a^{-1}, a^{-2}, \ldots\) modulo \(d\).
Let \(x_{k_{0}}\) the first element such that \(x_{k_{0}} \equiv a^{-n}(\bmod d)\). We have either \(k_{0}=1\) or \(x_{k_{0}}=\) \(x_{k_{0}-1} / a\); in both cases \(x_{k_{0}}<d<a^{n}<d a\) and therefore
\[x_{k_{0}} \in\left\{a^{n}-d, a^{n}-2 d, \ldots, a^{n}-(a-1) d\right\}\]
In this set no element is divisible by \(a\), so therefore the sequence will visit the value \(a^{n}\) in the next \(a-1\) steps.Like in the first solution, \(x_{k}\) is relatively prime to \(d\) and \(x_{k}<a d\) for all \(k\). Let
\[S=\left\{x \in \mathbb{Z}_{>0}: 0<x<a d, \operatorname{gcd}(x, d)=1\right\} \quad \text { and } \quad f: S \rightarrow S, f(x)= \begin{cases}x+d & \text { if } a \nmid x \\ x / a & \text { if } a \mid x\end{cases}\]
So, we have \(x_{1}=1\) and \(x_{k+1}=f\left(x_{k}\right)\). Notice that the recurrence formula is invertible. Suppose that \(f(x)=y\) for some \(x, y \in S\). If \(y>d\) then \(y-d \in S\) but \(a \cdot y \notin S\); otherwise, if \(y\[f^{-1}(y)=\left\{\begin{array}{ll} y-d & \text { if } y>d, \\ a \cdot y & \text { if } y<d \end{array} \quad \text { for all } y \in S\right.\]
It follows that the sequence is periodic, and therefore attains the initial value 1 infinitely many times. Let \(k_{1}>1\) be an index such that \(x_{k_{1}}=1\). Then\[x_{k_{1}}=1, \quad x_{k_{1}-1}=f^{-1}(1)=a, x_{k_{1}-2}=f^{-1}(a)=a^{2}, \ldots, \quad x_{k_{1}-n}=a^{n}\]
Like in the first solution, \(x_{k}\) is relatively prime to \(d\) and \(x_{k}<a d\) for all \(k\).
We wish to prove that there are \(n\) consecutive decreasing indices. Let \(m_{0}=0\) and \(m_{k}\) be the \(k\)-th smallest decreasing index (an index \(k\) is decreasing if \(x_{k}=x_{k-1} / a\) ) and define a sequence \(\left(y_{k}\right)_{k}=\left(x_{m_{k}}\right)_{k}\), i.e. the subsequence consisting only of elements with decreasing indices. For each \(k \geqslant 1\) we can write
\[y_{k+1}=\frac{y_{k}+z_{k} d}{a}\]
for some \(z_{k} \in{0,1, \ldots, a-1}\), where \(z_{k}=0\) if and only if \(y_{k}\) and \(y_{k+1}\) are consecutive elements in the original sequence. Then\[y_{k}=\frac{1+\left(z_{0}+z_{1} a+\cdots+z_{k-1} a^{k-1}\right) d}{a^{k}}\]
because \(y_{k}\) is bounded the sequence is (eventually) periodic. Consider some \(y_{u}=y_{u+v}\) where \(v \geqslant 1\). We can write\[y_{u}=\frac{1+\left(z_{0}+z_{1} a+\cdots+z_{u-1} a^{u-1}\right) d}{a^{u}}\]
and\[y_{u+v}=\frac{1+\left(z_{0}+z_{1} a+\cdots+z_{u+v-1} a^{u+v-1}\right) d}{a^{u+v}}\]
and so\[\frac{1+\left(z_{0}+z_{1} a+\cdots+z_{u+v-1} a^{u+v-1}\right) d}{a^{u+v}}=\frac{1+\left(z_{0}+z_{1} a+\cdots+z_{u-1} a^{u-1}\right) d}{a^{u}}\]
Rearranging gives\[\frac{a^{v}-1}{d}=z_{0}+z_{1} a+\cdots+z_{v-1} a^{v-1}+\left(z_{v}-z_{0}\right) a^{v}+\cdots+\left(z_{u+v-1}-z_{u-1}\right) a^{u+v-1}\]
Since \(d>a^{n} / a=a^{n-1}\) the LHS is strictly less than \(a^{v-n}\). This implies that on the RHS, the coefficients of \(a^{v-n}, a^{v-n+1}, \ldots\) must all be zero, i.e. \(z_{v-n}=z_{v-n+1}=\cdots=z_{v-1}=0\). This implies that there are \(n\) consecutive decreasing indices in the original sequence.