# Is the Following Statement in Modular Arithmetic Correct?

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?

• Well, $a+d\equiv a \pmod d$ for any $a$, yes? I mean, all it says is that $d\,|\,(a+d)-a$ which is clearly true. – lulu Mar 14 '17 at 18:28
• @lulu But they are saying that $f_{i+1} = (f_i + d - r') \mod M = (f_i + d - r') \mod d$. Why is that true? – Banach Tarski Mar 14 '17 at 18:30
• Oh, I see. I didn't understand the question. I'll look again... – lulu Mar 14 '17 at 18:32
• Well, I think they must be using additional information about the data. Say we take $r'=M$. Then I certainly have $r'\equiv M\pmod d$. your first congruence just tells us that $f_2\equiv f_1 +d\pmod M$ but that tells us nothing about $f_2\pmod d$. Unless I am still missing the point of course. – lulu Mar 14 '17 at 18:37
• @lulu I have modified the problem statement – Banach Tarski Mar 14 '17 at 18:51

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.