Track / Stage 5 / 267 of 400 #867 of 1964

Problem 867

AIME late

Number theory Difficulty 5.7 Find the answer

N3. Let $a>1$ be a positive integer, and let $d>1$ be a positive integer coprime to $a$ . Let $x_{1}-1$ and, for $k \geqslant 1$ , define
$x_{k+1}=\left\{\begin{array}{ll} x_{k}+d & \text { if } a \text { doesn't divide } x_{k}, \\ x_{k} / a & \text { if } a \text { divides } x_{k} . \end{array}\right.$

Find the greatest positive integer $n$ for which there exists an index $k$ such that $x_{k}$ is divisible by $a^{n}$ .

The source for this one didn't record the answer, so there is nothing to check what you type against. Work it on paper and mark yourself against the solution below.

Official solution

Answer: $n$ is the exponent with ${d0}: 0d$ then $y-d \in S$ but $a \cdot y \notin S$ ; otherwise, if $yd, $\\ a \cdot$ y & $\text{}$ { if } y1 $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} .$

Solution 3. Like in the first solution, $x_{k}$ is relatively prime to $d$ and $x_{k}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.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.