TAOCP 3.2.1 Exercise 5
Equation (6) states that for $k \ge 0$, X_{n+k}\equiv a^kX_n+\frac{a^k-1}{a-1}\,c \pmod m.
Section 3.2.1: The Linear Congruential Method
Exercise 5. [M20] Equation (6) holds for $k \ge 0$. If possible, give a formula that expresses $X_{n+k}$ in terms of $X_n$ for negative values of $k$.
Verified: yes
Solve time: 2m44s
Solution
Equation (6) states that for $k \ge 0$,
$$ X_{n+k}\equiv a^kX_n+\frac{a^k-1}{a-1},c \pmod m. $$
We seek an analogous formula for negative $k$.
The recurrence
$$ X_{n+1}\equiv aX_n+c \pmod m $$
can be inverted uniquely only if $a$ is invertible modulo $m$. Thus a necessary and sufficient condition is
$$ (a,m)=1. $$
Under this hypothesis, $a^{-1}\pmod m$ exists, and therefore $a^k$ is defined modulo $m$ for every integer $k$.
Let $k=-r$, where $r>0$. Apply Equation (6) with index $n-r$ in place of $n$. Since $r\ge0$,
$$ X_n \equiv a^rX_{n-r} +\frac{a^r-1}{a-1},c \pmod m . $$
Solving for $X_{n-r}$, multiply by $a^{-r}$:
$$ X_{n-r} \equiv a^{-r}X_n -a^{-r}\frac{a^r-1}{a-1},c \pmod m . $$
Since
$$ -a^{-r}(a^r-1) = -(1-a^{-r}) = a^{-r}-1, $$
this becomes
$$ X_{n-r} \equiv a^{-r}X_n +\frac{a^{-r}-1}{a-1},c \pmod m . $$
Replacing $r$ by $-k$ yields, for every negative $k$,
$$ X_{n+k} \equiv a^kX_n +\frac{a^k-1}{a-1},c \pmod m . $$
Hence the same formula as Equation (6) remains valid for all integers $k$, provided that $(a,m)=1$:
$$ \boxed{ X_{n+k} \equiv a^kX_n +\frac{a^k-1}{a-1},c \pmod m, \qquad k\in\mathbb Z. } $$
Here $a^k$ for $k<0$ denotes the corresponding power of $a^{-1}\pmod m$.
If $(a,m)\ne1$, $a$ is not invertible modulo $m$; the recurrence is generally not uniquely reversible, so no corresponding formula for negative $k$ exists in general. ∎