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?

  • $\begingroup$ 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. $\endgroup$ – lulu Mar 14 '17 at 18:28
  • $\begingroup$ @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? $\endgroup$ – Banach Tarski Mar 14 '17 at 18:30
  • $\begingroup$ Oh, I see. I didn't understand the question. I'll look again... $\endgroup$ – lulu Mar 14 '17 at 18:32
  • $\begingroup$ 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. $\endgroup$ – lulu Mar 14 '17 at 18:37
  • $\begingroup$ @lulu I have modified the problem statement $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.