3
$\begingroup$

Let $n$ and $k$ be coprime, and let $1\leq b \leq n$. The sequence $k, 2k ,3k, \ldots$ reduced modulo $n$ to the range $1, \ldots, n$, will eventually run through every integer in the range $1, \ldots, n$, since $k\perp n$. In particular it will eventually hit $-1$. Before it hits $-1$, how many integers will it visit in the range $1, \ldots, b$?

$\endgroup$
  • $\begingroup$ Technically, $-1$ is not in the range $1..n$ $\endgroup$ – Joffan Jul 27 '16 at 16:10
  • 1
    $\begingroup$ If the inverse of $n-b$ in $\mathbb Z_n$ is $k$, then the sequence will hit $-1$ at the $k$-th index. $\endgroup$ – Elaqqad Jul 27 '16 at 16:11
  • $\begingroup$ @Joffan $-1$ modulo $n$, of course. $n-1$, if you prefer. $\endgroup$ – Jack M Jul 27 '16 at 16:14
  • $\begingroup$ Also the answer depends on the sizes of $b, k, n$ relative to each other, as this can determine whether a multiple of $k$ steps over the region $1..b-1$ or whether successive multiples can find target values before wrapping the modulus. $\endgroup$ – Joffan Jul 27 '16 at 16:16
  • 2
    $\begingroup$ And there is no general expression for the inverse of $n-b$ modulu $n$. it can be anything. Finding the inverse $k=(n-b)^{-1}$ requires computing the inverse in $\mathbb{Z}_n$ which is equivalent to running the sequence $k,2k,....$ until it its $-1$ $\endgroup$ – Elaqqad Jul 27 '16 at 16:23
1
$\begingroup$

I wasn't able to solve the problem completely, but I did find an interesting identity satisfied by the sequence.

Let $n$ and $k$ be coprime and let $1\leq b<n$. We'll write $g(n, b, k)$ for the number referred to in the question.

Before I get to that, I'll need a formula for the following quantity:

We'll write $f(b, k, i)$ for the number of integers congruent to $i$ modulo $k$ in the range $1, ..., b$.

It's not hard to get a formula for $f$. The congruence classes modulo $k$ of the integers $1, 2, 3, ...$ form a periodic sequence of period $k$. The number of periods in the range $1, ..., b$ is exactly $\lfloor \frac b k \rfloor$, and each one will contain exactly one integer congruent to $i$. There will then generally be a partial period, which may or may not contain an extra integer congruent to $i$, depending on the value of $i$. Specifically:

If $b$ is a multiple of $k$, then there is no extra partial period, and we have $$f(b, k, i)=\frac b k$$ Otherwise, let $b_k$ and $i_k$ be the reductions modulo $k$ of $b$ and $i$ to the range $1, ..., k$. Then if $b_k\geq i_k$, there is an extra integer congruent to $i$ in the partial period, and $$f(b, k, i)=\lfloor\frac b k\rfloor+1$$ And if $b_k<i_k$ $$f(b, k, i)=\lfloor\frac b k\rfloor$$

Now let's look at $g$. The sequence $(ik)_i$ will begin by running through all of the multiples of $k$ in the range $1, ..., n$. Assuming it doesn't pass through $n-1$, it will then wrap around and end up at the value $-n$, reduced modulo $k$ to the range $1, ..., k$. It will then run through all values congruent to $-n$ modulo $k$, before wrapping around once more to the value $-2n$. It will wrap around some number $r$ times, finally reaching the value $-rn$, then run through all values congruent to $-rn$, the last of which will be $n-1$. From this it follows that the value of $r$ is $n^{-1} - 1$ modulo $k$, where $n^{-1}$ denotes the inverse of $n$ modulo $k$, and the value is taken in the range $1, ..., k$.

This description of the sequence $(ik)_i$ implies that

$$g(n, b, k) = \sum_{i=0}^r f(b, k, -in)$$

When $k$ divides $b$, this reduces to

$$g(n, b, k) = (r + 1)\frac b k = n^{-1}_k \frac b k$$

Where $n^{-1}_k$ denotes the inverse of $n$ modulo $k$, taken in the range $1, ... k$. When $k$ does not divide $b$, however, we obtain

$$g(n, b, k) = n^{-1}_k \lfloor\frac b k\rfloor + N$$

Where $N$ is the number of integers $i$ in the range $0, ..., r$ such that $(-in)_k\leq b_k$. But hang on... by construction, $r+1$ is the smallest value such that $-n(r+1)\equiv -1\mod k$. So $N$ is almost $g(k, b, -n)$. There are two problems:

  1. We're running the sequence $(-n)i$ starting at $i=0$, but in the definition of $g$, we start at $i=1$. This is not such a big problem since for $i=0$, $-ni\equiv k$ modulo $k$, which will be less than or equal to $b$ precisely when $b_k=k$.
  2. The sequence stops short of reaching $-1$ modulo $k$, whereas in the definition of $g$, if $k-1$ is less than or equal to $b_k$, it would be included in our count.

If $b_k=k$, these two effects cancel each other out, and $N=g(k, b, -n)$. The problem is when $b_k = k-1$. In that case, $N=g(k, b, -n) - 1$.

When $b$ is not a multiple of $k$, and $b\not\equiv -1\mod k$: $$g(n, b, k) = n^{-1}_k\lfloor \frac b k\rfloor + g(k, b, -n)$$ when $b$ is not a multiple of $k$, and $b\equiv-1\mod k$: $$g(n, b, k) = n^{-1}_k\lfloor \frac b k\rfloor + g(k, b, -n) - 1$$ where the arguments of $g$ on the right hand side are taken modulo $k$ in the range $1, ..., k$.

I've tested this identity by computer. It's possible there are some minor errors in the proof, but I'm confident the result is correct.

$\endgroup$
  • $\begingroup$ The question and this answer remind me of Eisenstein's proof of quadratic reciprocity. I don't know whether this is a coincidence or there's a real connection. en.wikipedia.org/wiki/… $\endgroup$ – Ethan Bolker Oct 29 '16 at 15:04

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.