You are given the following arithmetic progression modulo M.
$S = u, u+d, u+2d, \dots, u+nd \mod M$
Let's group this sequence $S$ into chunks of strictly increasing sequences $S_0, S_1, S_2, \dots, S_k, S_{k+1}$ where $S_i = {f_i, f_i+d, f_i+2d, \dots e_i}$ (and $S_0 = u, u+d, \dots, e_0$) such that $e_i > f_{i+1}$ and $e_i + d \mod M = f_{i+1} \mod M$ and $S_i$ is strictly increasing modulo M.
It is given that $d < M$
Show that except for $f_0$, the sequence $f_1, f_2, \dots, f_{k+1}$ forms an arithmetic sequence modulo $d$ with common difference $-r'$ where $r' = M \mod d$, i.e.,
$$f_{i+1} = f_i - r' \mod d$$
I am reading this paper, and in Section 3, Claim 2 , they show the above statement using some modular arithmetic jugglery and I am unable to follow
Can someone please explain why this is true?
To avoid confusion, let me clarify that by "$a = b \bmod c$" I mean that $a$ is the remainder between $0$ and $c-1$ we get when we divide $b$ by $c$, whereas by "$a \equiv b \pmod c$" I just mean that $a$ and $b$ differ by a multiple of $c$.
Let $\ell_i$ be the length of $S_i$, so that the chunk $S_i$ consists of $$f_i, f_i + d, f_i + 2d, \dots, f_i + (\ell_i - 1)d,$$ which is an increasing sequence of integers between $0$ and $M-1$. Moreover, because $S_i$ stops there, the next term $f_i + \ell_i d$ is bigger than $M$, and gives us the first term of $S_{i+1}$: $$f_{i+1} = f_i + \ell_i d \bmod M = f_i + \ell_i d - M.$$
(To put it another way, since the last term of $S_i$ is less than $M$, and $d<M$, adding $d$ to it overshoots by less than $M$, so we only need to subtract $M$ once to get back to the range $0$ to $M-1$.)
So, since $f_i + (\ell_i-1)d$ was still less than $M$, $f_i + \ell_i d$ is less than $M+d$, so $f_{i+1}$ is less than $d$. This tells us that $f_1, f_2, \dots$ actually is a sequence of remainders modulo $d$.
The other half of checking that $f_1, f_2, \dots$ is actually an arithmetic progression modulo $d$ is to show that the difference $f_{i+1} - f_i$ is constant modulo $d$. But $$f_{i+1} - f_i = (f_i + \ell_i d - M) - f_i = \ell_i d - M,$$ so $f_{i+1} - f_i \equiv -M \pmod d$. Moreover, this tells us that the common difference is exactly $-r' = (-M) \bmod d$, as desired.