Let $n, b, r^∗, t^* \in \mathbb{Z}$, with $0 \lt r^∗ \le n \lt r^∗t^∗$. Then there exist $r, t \in \mathbb{Z}$ with

$r \equiv bt \pmod n$, $\lvert r \rvert \lt r^∗$, and $0 < \lvert t \rvert \lt t^∗$.

Expanded proof from Shoup:

Observe $t^*$ must be at least 2, given $r^∗ \lt r^∗t^∗$.

For $i = 0, \dotsc, r^∗−1$ and $j = 0, \dotsc, t^∗−1$, we define the number $v_{ij} := i − bj$. Since we have defined $r^∗t^∗$ numbers, and $r^∗t^∗ \gt n$, two of these numbers must lie in the same residue class modulo $n$; that is, for some $(i_1, j_1) \ne (i_2, j_2)$, we have $v_{i_1j_1} \equiv v_{i_2j_2} \pmod n$.

But why ? Since the number of possible ($i,j$) pair is $r^*t^* \gt n$, two of them must collide in the same class module n. Alternatively, observe when the $ij$ of $v_{ij}$ is interpreted as the product of $i$ and $j$, the why becomes obvious due to the pigeonhole principle.

Moving on,

$$\begin{aligned} v_{i_1j_1} &\equiv v_{i_2j_2} \pmod n \\ i_1 - bj_1 &\equiv i_2 - bj_2 \pmod n \\ i_1 - i_2 &\equiv bj_1 - bj_2 \pmod n \\ i_1 - i_2 &\equiv b(j_1 - j_2) \pmod n \\ \end{aligned}$$

Setting $r := i_1−i_2$ and $t := j_1−j_2$, this implies:

1. $r \equiv bt \pmod n$, $\lvert r \rvert \lt r^∗$, since both $i_1$ and $i_2$ are less than $r^*$,
2. $\lvert t \rvert \lt t^∗$, since both $j_1$ and $j_2$ are less than $t^*$, and
3. either $r \ne 0$ or $t \ne 0$, since $(i_1, j_1) \ne (i_2, j_2)$.

It only remains to show that $t \ne 0$. Suppose to the contrary that $t = 0$. This would imply that $r \equiv 0 \pmod n$ and $r \ne 0$, which is to say that $r$ is a non-zero multiple of n; however, this is impossible, since $\lvert r \rvert \le r^∗ \le n$.

$\Box$