Question 96
Let $a \gt 1$ be a positive integer, and let $d \gt 1$ be a positive integer coprime to $a$. Let $x_1 = 1$ and, for all $k \ge 1$, recursively define
$$
x_{k+1} = \begin{cases} x_k + d & \text{if } a \text{ doesn't divide } x_k, \\ x_k/a & \text{if } a \text{ divides } x_k. \end{cases}
$$
Find the greatest positive integer $n$ (as a function of $a$ and $d$) for which there exists an index $k$ such that $x_k$ is divisible by $a^n$.
$$
x_{k+1} = \begin{cases} x_k + d & \text{if } a \text{ doesn't divide } x_k, \\ x_k/a & \text{if } a \text{ divides } x_k. \end{cases}
$$
Find the greatest positive integer $n$ (as a function of $a$ and $d$) for which there exists an index $k$ such that $x_k$ is divisible by $a^n$.