0

Let's start with a modulus $m=5$ (this could be any integer) a step size $s=2$ (this must be relatively prime with $m$), and an initial starting value modulo $m$ of $i=1$. In this particular case, we have:

m: 0  1  2  3  4
      x

When we advance by one step, we have:

m: 0  1  2  3  4
            x

If we advance 1 more step, we have:

m: 0  1  2  3  4
   x

We can easily work it out that it will take 4 steps total to reach $4 \bmod 5$.

Is there a formula for calculating the number of steps it will take to reach an arbitrary remainder modulo $m$ from an arbitrary starting point modulo $m$ given a step size $s$ that is relatively prime with $m$ (Note that $s$ may be larger than $m$)?

Adam
  • 679

1 Answers1

0

Let $n$ be the number of steps, starting at zero, let $a$ be the starting number, and $b$ be the ending number. Then we want to know $n$, depending on $a$, $b$, $s$, and $m$ such that $a+ns \cong b \pmod{m}$. That is we want $n$ such that $$ n s \cong b - a \pmod{m} \text{.} $$

By Bezout's lemma, since you assume $\gcd(s,m) = 1$, there are integers $x, y$ such that $xs+ym = 1$. Given $s$ and $m$, $x$ and $y$ can be explicitly computed using the extended Euclidean algorithm. Then $$ (b-a)(xs+ym) = (b-a) $$ Reducing modulo $m$, this says $$ (b-a)xs \cong b-a \pmod{m} \text{.} $$ So $n \cong (b-a)x \pmod{m}$.

Eric Towers
  • 67,037