Question 28
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 $k \geqslant 1$, 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$ 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$ for which there exists an index $k$ such that $x_{k}$ is divisible by $a^{n}$.