Let $A, M$ be two positive integers such that $A < M$.

Define the sequence $\{c_n\}$ satisfies $0 \le c_n < M$ and $c_n \equiv A n (\mathrm{mod}\ M)$ for $n \ge 1$.

Moreover let $n_1 = 1$ and if $c_{n_k} > 0$, we define

$$ n_{k + 1} = \min \{n: n > n_k, c_n < c_{n_k} \}. $$

Hence $A n_{k+1}$ is the first positive multiple of $A$ that yields a residual less than $c_{n_k}$.

Following theorem shows the recurrence relation of the sequence $\{n_k\}$.

Theorem 1

Suppose that $c_{n_{k+1}} > 0$, then we have

$$\begin{align} n_{k+2} = \left\lceil \frac{c_{n_k}}{c_{n_{k+1}}} \right\rceil n_{k+1} - n_k. \end{align}$$

Following proof is based on the proof of brob26.

Proof: Define $\alpha = \left\lceil \frac{c_{n_k}}{c_{n_{k+1}}} \right\rceil$. Note that

$$\begin{align} A (\alpha n_{k+1} - n_k) \equiv \left\lceil \frac{c_{n_k}}{c_{n_{k+1}}} \right\rceil c_{n_{k+1}} - c_{n_k} ~~(\mathrm{mod}\ M), \end{align}$$

and

$$\begin{align} 0 = \frac{c_{n_k}}{c_{n_{k+1}}} c_{n_{k+1}} - c_{n_k} \le \left\lceil \frac{c_{n_k}}{c_{n_{k+1}}} \right\rceil c_{n_{k+1}} - c_{n_k} < \left( \frac{c_{n_k}}{c_{n_{k+1}}} + 1\right) c_{n_{k+1}} - c_{n_k} = c_{n_{k+1}}. \end{align}$$

Then by the definition of $n_{k+2}$, we know that $n_{k+2} \le \alpha n_{k+1} - n_k$.

Next, we will show that for $1 \le t \le \alpha$, there holds $n_{k+2} - t n_{k+1} + n_k \ge 0$.

For $t = 1$, $n_{k+2} - n_{k+1} + n_k \ge 0$ holds apparently. Furthermore, assume that for $1 \le t < \alpha$ we have $n_{k+2} - t n_{k+1} + n_k \ge 0$.

Now observe that

$$\begin{align} A (n_{k+2} - t n_{k+1} + n_k) \equiv c_{n_{k+2}} - t c_{n_{k+1}} + c_{n_k} ~~(\mathrm{mod}\ M). \end{align}$$

Since $t c_{n_{k+1}} \ge c_{n_{k+1}} > c_{n_{k+2}}$, we have $c_{n_{k+2}} - t c_{n_{k+1}} + c_{n_k} < c_{n_k}$.
And, we also have

$$\begin{align} c_{n_{k+2}} - t c_{n_{k+1}} + c_{n_k} \ge - (\alpha - 1) c_{n_{k+1}} + c_{n_k} > 0. \end{align}$$

Thus $n_{k+2} - t n_{k+1} + n_k > 0$. Then by the definition of $n_{k+1}$, we must have $n_{k+1} \le n_{k+2} - t n_{k+1} + n_k$, i.e., $n_{k+2} - (t+1) n_{k+1} + n_k \ge 0$.

Consequently, $n_{k+2} - \alpha n_{k+1} + n_k \ge 0$, or equivalently $n_{k+2} \ge \alpha n_{k+1} - n_k$.

As a conclusion, there holds $n_{k+2} = \alpha n_{k+1} - n_k$.

☐