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\)